Coding 공부

N = int(input())

dp = [[0]*10 for _ in range(N)]


temp = [-1,1]
for i in range(N):
    for j in range(10):
        if i == N-1:
            if j == 0:
                continue
        if i == 0:
            dp[0][j] = 1
        else:
            for k in temp:
                nx = j+k
                if 0<=nx<10:
                    dp[i][j] += dp[i-1][j+k]

            
print(sum(dp[N-1])%1000000000)

dp 관련 문제이다.

이전 x-1축과 x축의 j 값이 1이 차는 경우를 더해주면 되는 것이다. 그리고 마지막 N-1 축까지 왔을 때 그때까지 누적된 수를 더해주면 된다.

# 1149번 RGB 거리

#  RGB 거리엔 N개의 집 1~N 순서대로
# 빨 초 파 중 하나
# 비용의 최소값 구하기
# 1번집의 색 != 2번집의 색
# N번집의 색은 N-1 번집의 색과 같지 않아야한다.

N = int(input())
# RGB
arr = [list(map(int,input().split())) for _ in range(N)]
INF = float('inf')
dp = [[INF] *3  for _ in range(N)]
for i in range(3):
    dp[0][i] = arr[0][i]

for x in range(1,N):
    for y in range(3):
        for z in range(3):
            if y != z:
                dp[x][y] = min(dp[x][y],dp[x-1][z]+arr[x][y])

print(min(dp[N-1]))

처음엔 그냥 dfs를 이용해서 풀어볼려다가, 입력 N이 1000까지라, 3^1000은 시간초과가 날것 같아서 dp로 선회했다.

dp에서 제일 어려운건 동적프로그래밍을 저장할 공간을 설계하는 것 같다. 이 문제를 풀때에 어떻게하면, 이전위치의 저장정보와 최소값 저장할지 고민했었다.

그 해결방법으로 index를 이용했다. dp를 저장하는 y축 index가 동일하지않으면 된다는 점을 착안하여, dp를 설계했다.

# 12865 평범한 배낭



N,K = map(int,input().split())

arr = [list(map(int,input().split())) for _ in range(N)]

dp = [0]*(K+1)
for i in range(N):
    weight,value = arr[i]
    for k in range(K,-1,-1):
        if k + weight <= K:
            if k == 0:
                dp[k+weight] = max(dp[k+weight],dp[k]+value)
            else:
                if dp[k]:
                    dp[k+weight] = max(dp[k+weight],dp[k]+value)
print(max(dp))

아마 동적프로그래밍 관련 유명한 문제인걸로 알고 있다.

풀어보고 다른 사람 코드를 보니깐, 2개의 리스트를 만들어서 하나는 최대값이 되는 값을 저장하는 리스트와, 사용여부를 나타내는 리스트를 2개를 두고 하는 경우가 많았다.

그러나 나같은 경우엔 한가지 리스트를 주고, dp의 인덱스값이 0일때는 최대 무게를 넘지 않는한 바로 더해주었고, 그 외에는 해당 인덱스에 저장된 값이 존재하는 경우에만 하도록 했다. 이렇게 했을시에 사용여부를 따로 만들지 않아도 되었다.

여기서 중요했던 점은 역으로 판단을 해줘야했던 것이다. 앞에서부터 순서대로 할시에, 그대로 그 전거가 다음거에 영향을 주기 때문에 끝에서 0으로 가는 것이 중요했다.