수학과의 개발자 도전기

• 백준 코딩테스트 매일 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)

-정답 풀이 

•  5를 기준으로 계산해야 최소값을 구할 수 있다는 것은 생각했는데, #10,11 라인을 생각을 못했다. 참고해서 알아두기 

2. 1463번: 하나도 모르겠음,,  -> 코드 계속 보면서 이해하기위해 노력하기 

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

-정답 출처: https://infinitt.tistory.com/247

3. 1003번 

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

- 초기값 설정하기 

=> 위의 표를 리스트로 옮기면 다음과 같다. 

- 문제 풀이 핵심 원리: 

- 10번 문장이 들어있는 이유: zero의 길이보다 짧은 리스트(num이 1,2,3일경우 )가 입력되었다면 기존의 값을 반환하면 되기 때문이다.