[코딩테스트]#3. 백준 2839번, 1463번, 1003번

백준/DP

[코딩테스트]#3. 백준 2839번, 1463번, 1003번

ydin 2021. 12. 10. 13:56

백준 코딩테스트 매일 3문제씩 푸는 것이 목표(동적프로그래밍,그리디,탐색 50문제씩 푸는 것)

동적 계획법을 사용해야하는 문제

초기값으로 설정할 값이 명확
기존에 연산된 값을 재사용하는 메모이제이션이 있어야 함

메모이제이션: 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술

1. 2839번

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

-내가 작성한 틀린 풀이

조건문으로 풀면 복잡해짐

n=int(input())
cnt=0

#5의 배수일때 
if n%5==0:
    cnt= n//5
    
#3의 배수일때 
elif n%3==0:
    if (n//5)+1 < (n//3):
        cnt = (n//5)+1
    else: 
        cnt=n//3
        
#3,5의 배수 아니지만 합으로 표현가능할 때        
elif (n%5)%3==0:
    a=n//5
    b=(n%5)
        
#3,5의 합으로 나타낼 수 없을 때 
else:
    cnt=-1
    
print(cnt)

-정답 풀이