[일반] 피린이 벽을 만났는데 도움좀요

[코로나(lchbest10)]

https://www.acmicpc.net/problem/3687
dp문젠데 이거 max는 대충알겠는데 min은 점화식 구성이 되나요?? 진짜 규칙이 없는거같은데...

[Outersky(oomaga)]

min은 어떤 수로 나눠서 나머지에 따라 다를 듯? 값이 뱅뱅 돈다고

[Outersky(oomaga)]

5초 읽은 느낌은 그럼

[JO(satenruiko)]

이글 보고 궁금해서 풀어봤는데.. min은 먼저 성냥을 2,3,4,5,6,7개 사용해서 낼 수 있는 최소값을 손으로 구해보면 감이 금방 올꺼임

[코로나(lchbest10)]

근데 점화식이 세워져요? 최솟값 구성까진 했는데 일반화가 안되던데

[JO(satenruiko)]

세워지긴 세워짐 ㅋㅋ 윗 댓글에 2~7개 사용해서 낼 수 있는 최소값을 손으로 구해보라고 했는데 그뒤에 8~15개 사용해서 낼 수 있는 최소값도 손으로 구해보면 계속 똑같은걸 이어 붙인다는걸 깨달을 수 있을거임

[JO(satenruiko)]

예를 들어서 성냥 7개까지는 한자리 숫자를 만들 수 있고, 가장 많은 성냥을 소모하는 숫자가 8인데 성냥 7개를 소모함. 그러므로 8개부터는 아무리 최소값을 낸다고 해도 꼭 두자리 숫자를 만들어야함. 이런식으로 생각해보면 결국 DP[n] = min (DP[n-2] + DP[2], DP[n-3] + DP[3], DP[n-4] + DP[4], ..., DP[n-7] + DP[7]) (여기서 A + B는 A의 끝부분에 B를 이어붙인다고 가정)

[JO(satenruiko)]

뭔가 설명을 더 잘해주고 싶은데 풀어서 설명하기가 좀 어려운듯... 너무 많이 알려주면 푸는 입장에서 재미가 없고

[JO(satenruiko)]

한가지 예외 처리해야되는 케이스가 있는데 그것만 조심하고.. 이런 문제는 손으로 풀 수 있는 범위를 직접 노트에 써보고 규칙을 찾아보는걸 추천 ㅋㅋ 나도 DP 허접이라 잘 모를땐 이런식으로 먼저 접근해봄

[익명(1.249)]

문제 구질구질하네;;