백준 1937번 욕심쟁이 판다, 2437번 저울 (python)

욕심쟁이 판다 (1937번)

n * n 크기의 대나무 숲에서 판다가 움직이며 대나무를 먹을 때, 이동하는 칸의 대나무가 이전 칸의 대나무보다 많아야지만 이동 할 수 있을 때 판다가 이동 할 수 있는 칸의 수의 최대값을 출력합니다.

 

판다가 처음 이동을 시작하는 칸도 주어지지 않았기 때문에 모든 칸을 시작점으로 생각하여 이동을 해봐야 된다고 생각했습니다.

하지만, 모든 칸에서 이동 할 수 있는 칸의 수를 세는 것은 시간이 오래 걸릴 것으로 예상했습니다.

그래서, 각 칸마다 해당 칸에서 이동 할 수 있는 최대 칸의 개수를 저장해서 이전에 방문했던 칸이라면 다시 순회하지 않도록 했습니다.

 

dp 문제는 이전의 어떤 로직에 의해 발견된 값과 현재 다시 이 칸을 방문했을 때의 값을 비교해서 다른 값을 채워넣는 식의 문제가 있었기 때문에 이 문제에서는 각 칸에 방문했을 때 이 칸에 이전에 채워진 값 말고 다른 값이 채워지는 경우의 수는 없는지도 학인해보았습니다.

i,j 칸에서 이동 할 수 있는 최대 칸을 이미 찾은 경우, 어느 곳에서든 i,j 칸으로 다시 방문했을 때 i,j 에서 이동 할 수 있는 최대 칸의 개수는 동일합니다. 그러므로 다른 칸에서 이미 이동 가능한 최대 칸 수가 저장된 칸으로 이동했을 경우 dp 배열에 저장된 값을 바로 사용하도록 했습니다.

 

이러한 문제의 풀이법으로 피보나치 수열의 dp풀이법을 사용해보았습니다.

def pibo(num):
    if dp[num]!=0:
        return dp[num]
    
    dp[num]=pibo(num-2) + pibo(num-1)
    return dp[num]

위처럼 dp에 저장된 값이 있을 경우 dp 값을 바로 반환해 재귀 호출양을 줄여줍니다.

dp에 저장된 값이 없을 경우 재귀 호출을 통해 이전에 저장된 값을 찾아 새로운 값을 넣어주도록 해주고 해당 값을 반환해줍니다.

 

위 풀이법처럼 칸을 이동할 때 해당 칸에 이미 저장된 값이 있다면 해당 값을 사용하고, 아직 저장된 값이 없다면 해당 칸에서 이동 가능한 최대 칸 수를 구한 뒤, 해당 칸 수를 반환해줄 수 있도록 해주었습니다.

def recursion(x,y):
    global n
    
    if dp[x][y]!=1:
        return dp[x][y]
    
    maxMove=1
    for i in range(4):
        nx,ny=x+dx[i],y+dy[i]
        
        if not (0<=nx<n and 0<=ny<n) or bamboo[nx][ny]<=bamboo[x][y]:
            continue
        
        maxMove=max(maxMove,1+recursion(nx,ny))
    
    dp[x][y]=maxMove
    return dp[x][y]

모든 칸을 시작 칸으로 해서 recursion을 호출해주었고, 반환 받은 값 중 가장 큰 값이 답이 됩니다.

 

 

 

 

저울 (2437번)

N개의 저울추가 주어질 경우 해당 저울 추로 측정 할 수 없는 무게 중 최소값을 구하는 문제입니다.

 

우선 최소값을 구하는 문제이므로 주어진 저울 추를 오름차순으로 정렬해준 뒤 만들 수 있는 무게를 확인해 보았습니다.

 

처음에는 감이 안잡히고 계속 dynamic programming을 사용하려는 생각이 들어 풀이에 대한 생각이 잘 나지 않았습니다.

 

그래서, 예제 입력에서 주어진 저울 추로 만들 수 있는 무게를 한 번 구해보았습니다.

// 1 1 2 3 6 7 30 으로 만들 수 있는 무게

// 1 사용
1

// 1 1 사용
1 2

// 1 1 2 사용
1 2 3 4

// 1 1 2 3 사용
1 2 3 4 5 6 7

// 1 1 2 3 6 사용
1 2 3 4 5 6 7 8 9 10 11 12 13

// 1 1 2 3 6 7 사용
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

// 1 1 2 3 6 7 30
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 30 31 32 33 34 35 ...

위와 같이 나열을 해보니, 가장 큰 30을 사용했을 때 만들 수 있는 무게 중 중간에 빈 공간이 생기게 되어 여기서 답이 발생하는 것을 알게 되었습니다.

 

그래서 여기서 예제 입력을 조금 바꿔서 생각을 해보았습니다.

// 1 1 2 3 사용
1 2 3 4 5 6 7

// 1 1 2 3 7 사용
1 2 3 4 5 6 7 8 9 10 11 12 13 14

// 1 1 2 3 8 사용
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

위의 경우를 살펴보면, 1 1 2 3의 추에서 7, 8이 추가 될 경우 1 1 2 3의 추만을 사용해서 만들 수 있는 무게에 7, 8이 추가되었을 때의 무게가 추가되는 것을 볼 수 있습니다. (8이 추가될 경우 만들 수 있는 무게 중 자기 자신인 8이 추가되었습니다.)

이처럼 이전까지 추로 만들 수 있는 무게들에 새로 추가된 추의 무게가 더해져서 새로운 무게들이 만들어지는데, 새로 들어온 추의 무게가 어느정도 크다면 중간에 빈 공간이 생길 수도 있을 것이라는 생각이 들었습니다.

 

그래서 1 1 2 3에 9를 한 번 추가해보았습니다.

// 1 1 2 3 사용
1 2 3 4 5 6 7

// 1 1 2 3 9 사용
1 2 3 4 5 6 7 9 10 11 12 13 14 15 16

9를 추가했을 때 만들 수 없는 숫자가 생기게 되었습니다.

1 1 2 3으로 만들 수 있는 무게 중 가장 큰 7과 새로 들어온 추로 만들 수 있는 무게인 9 사이에 빈 공간이 만들어져 만들 수 없는 무게가 생기게 되었습니다.

 

여기서 착안하여 정렬된 추에서 이전까지 만들 수 있는 가장 무거운 무게와 새로운 추의 무게를 비교했을 때 새로운 추의 무게가 2 보다 더 크게 될 경우, 중간에 빈 공간이 발생해 만들지 못하는 무게가 생긴다고 생각했습니다.

예제 입력 또한, 7까지는 이전에 만들 수 있는 무게 중 가장 큰 값이 새로 들어온 추의 무게보다 항상 컸기 때문에 빈공간이 생기지 않았고 30은 이전의 추들로 만들 수 있는 무게인 20보다 10만큼 더 크기 때문에 중간에 빈 공간이 생기게 되었습니다.

 

그러므로 이전까지 만들 수 있는 무게의 최대값보다 새로 들어온 추의 무게 값이 2만큼 더 클 경우 이전까지 만들 수 있는 무게의 최대값+1이 답이 됩니다.

N=int(input())
weights = list(map(int,input().split()))
weights.sort()

answer=1
for i in range(N):
    if answer<weights[i]:
        break
    answer+=weights[i]
print(answer)

 

 

 

 

오늘은 어제 예고한대로 그리디 문제와 디피 문제를 한 문제씩 풀어봤습니다. 그리디의 경우 아직은 미숙하다고 생각이 들기 때문에 좀 더 많은 문제를 풀어야 겠다는 생각이 들었습니다.