-문제:https://www.acmicpc.net/problem/2839

 

처음에는 5를 기준으로 하고, 나머지는 3키로 봉지로 충당하면되겠지 생각했는데, 정확하게 n키로를 5와 3으로 맞춰야 정답이다

5를 기준으로 생각하는 것 맞지만, 18 같은 경우는 3*6도 되고, 15+3도 되기 때문에 이거를 어떻게 해야할지 몰랐다 

나름 dp로 풀어본다고 했는데 틀린 답이 나왔다 

 

-정답 풀이:

while문을 돌리면서 5의 배수이면 그대로 계산하고, 아닌 경우는 3을 감소시키면서 지켜본다 

while문에서 출력이 되지 않으면 n<0인 상황이 되어 while문을 나오는데, 그 경우에는 -1을 출력해주면 된다 

n=int(input())
dp=[0]*5001
dp[3],dp[5]=1,1
bag=0
while n>=0:
    if n%5==0:
        bag+=n//5
        print(bag)
        break
    else:
        n-=3
        bag+=1
else:
    print(-1)

 

-틀린 풀이: 

n=int(input())
dp=[0]*5001
dp[3],dp[5]=1,1
bag=0
for i in range(6,n+1):
    if dp[i-5]!=0:
        bag= 1+dp[i-5]
    elif i%3==0:
        dp[i]=i//3
    else:
        print(-1)
        break
print(dp[n])

'백준 > Greedy' 카테고리의 다른 글

[그리디/백준] 11399번: ATM  (0) 2022.06.23
[그리디/백준] 11047번: 동전0 (2차)  (0) 2022.06.23
[백준] 2812번: 크게 만들기  (0) 2022.02.11
[백준] 10775번: 공항(다시)  (0) 2022.02.11
[백준] 2810번: 컵홀더  (0) 2022.02.11

-문제:https://www.acmicpc.net/problem/18353

이는 주어진 정보를 역순으로 한 뒤에

증가하는 가장 긴 수열의 길이를 구해

전체 길이에서 빼면 답이 나온다 

 

처음에는 for문 두개가 아니라 한개로 했는데, 이때 틀렸다. 

이유는 0부터 i번째까지 증가하는 수열을 찾아야하는데, for문이 하나면, 국소적으로 i랑 i-1번째랑만 비교하므로 전체적인 수열을 구할 수 없다. 

for문 두개를 이용하면 답이 나온다. 

 

여기에서 length[i]+=1의 위치가 for j~를 나올 때 수행돼야 정답이 나오는지 궁금했다. 

그래서 두가지 경우에 대해 결과를 도출해봤다

 

1.

for i in range(n):
    for j in range(i):
        if data[i]>data[j] and length[i]<length[j]: #큰 수가 수열에 포함되지 않는 경우          
            length[i]=length[j] #이전 수열 값 누적
    	    length[i]+=1

이 경우에는 length의 모든 원소가 0인데, 크기 차이가 있어야지 +1 연산이 가능하기때문에 

결국 length의 모든 원소가 0인 상태로 끝난다 (length=[0,0,0,0,0,0,0])

 

2. 

for i in range(n):
    for j in range(i):
        if data[i]>data[j]: #큰 수가
            if length[i] <length[j]: #수열에 포함되지 않을 경우
                length[i]=length[j] #이전 수열 값 누적
    	length[i]+=1

이 경우는 data[i]> data[j]이 아닌 경우에도 length[i]+=1 연산이 수행된다. 

length = [0,1,2,3,4,5,6]

정답은 인덱스 5의 값이 2여야 하고, 인덱스 6은 4, 인덱스 7은 5여야 한다 

 

-정답풀이: 

n=int(input())
array=list(map(int,input().split()))
length=[0]*n
data=[0]*n
for i in range(n):
    data[i]=array[n-1-i]
    
for i in range(n):
    for j in range(i):
        if data[i]>data[j]: #큰 수가
            if length[i] <length[j]: #수열에 포함되지 않을 경우
                length[i]=length[j] #이전 수열 값 누적
    length[i]+=1
            
print(n-max(length))

 

-틀린 풀이

n=int(input())
array=list(map(int,input().split()))
length=[0]*n
data=[0]*n
for i in range(n):
    data[i]=array[n-1-i]
    
for i in range(1,n):
    if data[i]>data[i-1]:
        if length[i]<length[i-1]:
            length[i]=length[i-1]+1
            
print(n-max(length))

-문제: https://www.acmicpc.net/problem/14501

 

이전에 풀었던 풀이는 여기에 있다 

여기에서 t[i]+i를 왜 하는지 모르겠다고 되어있는데, 이는 간단하다. i번째 날에 상담을 했다면 상담을 끝난 날부터 다른 상담을 할 수 있으므로, 다음 상담을 할 수 있는 날이 i+t[i]인 것이다. 이때의 상담료를 보면된다 

 

-정답 풀이: 

풀이 방법으로 0번부터 차례로 상담가능한 날짜들을 기준으로 상담료를 더하는 것으로 생각했다. 

그리고 index+data[index][0]인 날을 기준으로 또 상담을 진행하는 것이라고 생각했다. 

여기서 고민되었던 게, i+t[i]일부터 상담을 할 수 있다는 것이지, 이날에 꼭 상담을 해야하는 것은 아니다. 

이 이후에 날에 기간내에 끝낼 수 있고, 더 많은 돈을 벌 수 있는 날이 있을 수 있기에 순차적으로 하기엔 어렵다고 생각했다. 

그래서 잘 풀리지 않아서 답지를 봤다 

 

일단 순서는 끝 인덱스부터 시작해야 한다.(for i in range(n-1,-1,1))

인덱스가 거꾸로 가므로 max_value는 dp[i+1]을 의미. 

 

n=int(input())
t=[]
p=[]
dp=[0]*(n+1)
max_value=0

for _ in range(n):
    x,y=map(int,input().split())
    t.append(x)
    p.append(y)
    
for i in range(n-1,-1,-1):
    time=t[i]+i
    if time <= n:
        dp[i]=max(p[i]+dp[time],max_value)
        max_value=dp[i]        
    else:
        dp[i]=max_value
print(max_value)

 

 

 

-문제:https://www.acmicpc.net/problem/1932

이전에 풀었던 과정은 여기에 있다

-정답풀이:

이전에 풀었던 문제라서 풀이과정이 비교적 쉽게 생각이 났다. 

 

과정

열이 0이거나 행과 같은 경우는 해당 숫자에 바로 위 숫자를 더하면 된다(여기서 열==0 인 경우와 열==행인 경우 다르게 설정해야 한다)

이외의 경우는 왼쪽, 오른쪽 위의 값 중 최댓값을 더해주면 된다 

 

다만 indexError가 계속 발생했는데, 이는 처음에 data를 data=[[] for _ in range(n)]으로 초기화 했었다. 

여기서 list를 삽입하면 3중 리스트가 되어서 계속 났던 것이다

 

그래서 data=[]라고 초기화한 후, 분기문에서 이전 값들을 data의 값이 아닌 dp의 값으로 대체했더니 정답이 떴다  

n=int(input())
data=[]
for _ in range(n):
    data.append(list(map(int,input().split())))
dp=[[0]*n for _ in range(n)]
dp[0][0]=data[0][0]
for i in range(1,n):
    for j in range(0,i+1):
        if j==0:
            dp[i][j]= (dp[i-1][j]+data[i][j])
        elif i==j:
            dp[i][j]=dp[i-1][j-1]+data[i][j]
        else:
            dp[i][j]= data[i][j]+max(dp[i-1][j-1],dp[i-1][j])
        
            
print(max(dp[-1]))

+ Recent posts