9095번 - 1,2,3 더하기

DP문제인데 그냥 재귀로 풀어버렸습니다 하하...

N = int(input())

입력받을 횟수를 받고

for _ in range(N):
    cnt = 0
    ans = []    
    a = int(input())
    dp(0,a)
    print(cnt)

변수를 받아 재귀를 돌려줍니다.

def dp(start,end):
    global cnt
    if start >= end:
        cnt += 1
        return 

만약 start변수가 end와 같아지거나 더 커진다면 cnt를 하나 올리고 함수를 종료합니다.

    for i in range(1,4):
        if sum(ans) + i > end:
            continue

1,2,3을 사용하여 해당 숫자를 어떻게 만드는지가 관건이므로 1~3까지 for문 재귀를 통해 구현하겠습니다. 돌리다가 만약 저장해둔 숫자(1,1,1...) + i(1or2or3) 이 end보다 커진다면 continue를 써서 해당 for문은 스킵하겠습니다.

        ans.append(i)

만약 더해서 커지지 않는다면 해당 경우의 수를 구하기 위해 i를 ans배열에 추가하고

        dp(start+i,end)

재귀로 다시 들어가서 예를 들어 합이 4라면 1111 구하고

        ans.pop()

pop 해서 1112,1113,1114 다 continue에 막히고 111은 끝났으니 112실행 => 합산 4니까 cnt+1 이런씩으로 작동됩니다.

---

---

2579 - 계단 오르기

제대로 된 DP 문제입니다.
DP는 점화식을 세우는게 제일 중요하니 만큼 문제 분석도 잘 해야 사용이 가능합니다.

---

분석

해당 문제는 최대값으로 계단을 오르면 점수가 몇점인가 묻는 문제입니다.
최대값으로 오를 수 있는 경우가 두 가지가 있는데,

1. 바로 직전 계단에서 마지막 계단으로 올라올 때
2. 전전 계단에서 마지막 계단으로 올라올 때

이 두가지 경우입니다.

마지막 계단을 기준점으로 삼은 이유는 N번째 계단을 밟아야만 끝난다는 제약이 있기 때문입니다.

1번과 같은 경우는 계단을 연속으로 최대 두 번만 밟을 수 있다는 제약이 있으므로, 위의 그림에 그려둔 것과 같이 N-3번째 계단을 밟고 N-1번째 계단을 밟아야 마지막 계단인 N번째 계단을 밟을 수 있습니다.

반면, 2번과 같은 경우는 제약이 없으므로 N-2번째 계단을 밟고 바로 마지막 계단인 N번째 계단을 밟는 게 가능합니다.

이를 식으로 세워두면
1. DP(N-3)(N-3까지의 최대값) + stair(N-1)(N-1의 계단 점수) + stair(N)(N의 계단 점수)
2. DP(N-2)(N-2까지의 최대값) + stair(N)(N의 계단 점수)

라는 형식으로 세울 수 있습니다.

---

코드

N = int(input())
stair = []
for _ in range(N):
    a = int(input())
    stair.append(a)

일단 계단의 개수하고 계단에 적힌 값들을 입력받아줍시다.

if N == 1:
    print(stair[0])
elif N == 2:
    print(stair[0]+stair[1])

1을 입력받았을때와 2를 입력받았을때는 점화식 스타트가 N-3부터이기 때문에 예외로 저렇게 처리해줍니다.

else:
    #dp 초기화
    dp = [0]*301
    dp[0] = stair[0]
    dp[1] = stair[0]+stair[1]
    dp[2] = max(stair[0] + stair[2], stair[1] + stair[2])

dp 시작부분입니다. 0과 1, 2는 초기값을 지정해줍시다. 이것 또한 마찬가지로 점화식에서 나오는 최소 변수가 N-3부터이기 때문에 4번째 계단부터 실질적으로 점화식 사용이 가능하기 때문입니다.

    #dp 점화식
    for i in range(3,N):
        dp[i] = max(dp[i-3]+stair[i-1]+stair[i],dp[i-2]+stair[i])

위에 문제분석을 실시한대로

N-3,직전계단,마지막계단을 거쳐서 오는가
직전계단,마지막계단을 거쳐서 오는가

를 판단해주어 그중 더 큰 값을 갖는 값을 dp리스트에 담아주도록 합시다.

그러면 dp값은 결국 해당 계단 위치에서 가질 수 있는 최댓값의 모임이 되고
그중 제일 마지막 계단의 최댓값 => 결국 정답이니까

    print(dp[N-1])

을 해주면 성공적으로 정답을 도출할 수 있습니다.

---