100년 뒤 개발자 한승규입니다.

https://www.acmicpc.net/problem/2839

옛날에 풀었던 문제이지만, 동적 프로그래밍을 복습하는 과정에서 가장 기초적인 문제라 다시 한 번 풀어보았다.

문제를 풀고 나서 옛날에 풀었던 것을 확인 해보았는 데...

N = int(input())

for i in range(int(N/5)+1,0,-1):
    if (N-5*i)%3==0 and N-5*i>=0:
        print(int(i+(N-5*i)/3))
        exit()
if(N%3==0):
    print(int(N/3))
    exit()
else:
    print(-1)

어떻게 풀었는 지는 모르겠지만, 동적프로그래밍이 아니라 그냥 계산으로 푼 것 같다...

동적 프로그래밍답게 지난 계산을 기억할 배열을 만들고 해당 데이터가 존재한다면 그 데이터를 이용해서 현재 데이터를 만들 수 있게 했다.

import sys

N = int(sys.stdin.readline())

sugar = [-1 for i in range(N + 3)]

sugar[3] = 1
sugar[4] = -1
sugar[5] = 1

for i in range(6, N+1):
    if sugar[i-3] == -1 and sugar[i-5] == -1:
        sugar[i] = -1

    elif sugar[i-3] == -1:
        sugar[i] = sugar[i-5] + 1

    elif sugar[i-5] == -1:
        sugar[i] = sugar[i-3] + 1

    else:
        sugar[i] = min(sugar[i-3], sugar[i-5]) + 1

print(sugar[N])

3, 4, 5에 대한 값을 미리 넣어줘야 하는 데 배열을 N+1로 만들어버리면 index 에러가 발생해서

그냥 N+3만큼 미리 만들어버리고 시작했다.

그리고 후에는 반복문을 돌며 3번 전, 5번 전의 계산에서 유효한 값이 있다면 그 중 작은 값에서 +1을 한다

만약 둘 중 하나만 유효한 값이라면 그 값의 +1을 하고, 둘 다 유효하지 않다면 만들 수 없는 경우이기 때문에 -1로 만들어준다.