[JAVA] 백준 10564번 팔굽혀펴기

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

10564번: 팔굽혀펴기

이 문제는.. 접근을 잘 하면 쉽게 풀 수 있는 문제인데

그 접근을 잘못해서 한참 헤맸다ㅠㅠㅠㅠ...

DP로 풀기 위해, unique한 값을 가진 변수를 구해야 하는데

d[index][score] = sum 을 생각했다..

index는 상관없이 d[score][sum] = true 로 접근하면 바로 풀 수 있었다..

 

일단 index, score은 unique 하지 않다...  index는 아에 필요없다.
각 점수를 받고 그 점수가 누적되면서 그 점수, 누적점수를 독립적인 값으로 보고 접근했어야 했다.

N이 29, M이 7,3,2인 경우
1번째 : 3점 - 3번 팔굽혀펴기 -> 총 3번
2번째 : 2점 - 5번 팔굽혀펴기  -> 총 8번 
3번째 : 2점 - 7번 팔굽혀펴기  -> 총 15번
4번째 : 7점 - 14번 팔굽혀펴기 -> 총 29번

위와 같이 d[3][3] = true -> d[8][5] = true -> d[15][7] = true -> d[29][14] = true

이렇게 접근해서 풀 수 있는 문제였다.