[일반] BOJ 1424 새 앨범 이문제

[dawdw(49.170)]

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

분류는 dp로 되어있는데

그냥 구현으로 풀었습니다.

근데 도대체 어떻게 접근해야 dp 입니까

구글에 풀이도 없어서 도저히 모르겠네요 ㅜㅜ

[익명(119.70)]

도움이 못되서 미안한데 이거 풀이좀 알려주셈 그리디하게 구하면 답이 아닌건가? 항상 최대 곡 수를 수록하고 남는 곡이 있으면 +1해서 출력했는데

[Gravekper(gravekper)]

13

[익명(119.70)]

최대 곡 수 구할 때 13으로 나눠떨어지면 -1해서 최대 곡 수 구함

[지덕군(jidockun)]

그냥 greedy + brute-force 같은데

[익명(119.70)]

왜 brute-force인가요? greedy하게 수록하는 방법은 하나밖에 없지 않음?

[지덕군(jidockun)]

나머지가 13배수일때 꽉 채운 애들한테서 몇개 가져와서 채우는거 때문에 그랬는데 님은 어케 푸셨음??

[익명(119.70)]

일단 cd한개에 최대한 채운 다음에 최대한 채운 곡 수가 13의 배수라면 -1 한 수를 최대 곡 수로 함.

[익명(119.70)]

전체 곡 수를 최대 곡 수로 나누고 나머지가 있으면 +1한 값을 출력

[지덕군(jidockun)]

그렇게 하면 틀림.. 님 푼거 맞음??

[지덕군(jidockun)]

아 글쓴이분이 아니셨구나.. 아무튼 나머지 있을때 +1 안해도 되는 방법이 있으니 함 생각해보셈

[지덕군(jidockun)]

아 말 잘못했네 +1 하고서 나머지 13배수인 경우 처리해야하는데 이거 처리하려면 +1하는 방법도 있고 안하는 방법도 있음

[익명(119.70)]

아 나머지가 13의 배수일 수도 있네....왜 나머지가 항상 13아래라고 생각하고있었지 ..급 자괴감이.. ㅋㅋ

[익명(119.70)]

감사합니다