[백준 1943번] 동전 분배

난이도: 골드 III

문제 링크: https://www.acmicpc.net/problem/1943

1943번: 동전 분배

백준 1943번 문제 동전 분배

 

DP를 통해 접근할 수 있는 문제입니다.

그리디로 왜 안 되는지는... 잘 모르겠네요 ㅠ

 

모든 동전의 값의 합을 먼저 구하고,

이것이 홀수라면 반으로 나눌 수 없으므로 0을 출력하고 넘어갑니다.

짝수라면, 총 값의 반을 최대 기준으로, 만들 수 있다면 해당 테이블에 1을 기록하며 진행합니다.

이전 인덱스의 값을 참조하여 진행하기 때문에 탑-다운 방식으로 접근합니다.

탑-다운 방식이 궁금하다면 여기를 참고하세요.

 

채점 결과

ㅋㅋㅋㅋ

제가 코드 하나를 loop 밖에 적는 바람에 몇번 틀렸습니다 ㅠ

모든 동전의 값의 합이 홀수일 때 0이 두 번 출력되는 문제였어요.