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

저번에 접근법 틀렸다고 징징거렸던 사람임


아직도 정답이 안 나옴


남 코드 엿보면 코드도 간단한데

나는 생성기 / 최대 금민수값 / 출력함수 / 금민수 몇 개인지 세는 함수 / 금민수인지 판정하는 함수 

어쩌고 저쩌고 계속 붙이니까 240줄임.


코딩해서 원하는 의도대로 만들었고 의도대로 굴러가는데 정답이 안 나오는걸 대체 몇 번 겪는지 자괴감드네


풀이

1. 금민수 생성기를 만들어서 금민수 1022개 (1이상 10억 이하 금민수)를 전부 입력

2. 금민수의 합으로 나타낼 수 있는지 확인하기 위해 나누어 떨어지는지 확인

3. 안 되면 -1 출력, 

4. 나누어 떨어지는 것을 확인했으면 테이블을 참조해서 가장 큰 수부터 빼가면서, map에 카운팅

5. 계속 빼면 0이 나와야하는데 안 나오면 0이 나올 때까지 7을 더하고 4를 더 카운팅

6. vector에 작은 것 수부터 옮겨담아서 출력


결과

모든 수에 대응됨

그런데 '가장 짧은' 금민수를 출력하지 못함

100 넣으면 4 4 4 44 44 가 가장 짧은데 4 4 4 4 7 77을 뱉음. 77이 더 크니까 77을 할당하는거.


패착 원인

'가장 짧은 것' 부터 출력하라고 했으니 

빨리빨리 최적을 구하는 문제로 인식해서 DP라고 판단해야하는데

테이블 만들었으니 그거 그리디하게 때려박으면 된다고 생각한게 좆망한 원인인듯


아... 현타온다