인프런 커뮤니티 질문&답변

제가 이해한 방식이 맞는지 확인받고자 질문드립니다! 혹시 이해에 잘못된 부분이 있다면 알려주시면 감사하겠습니다 ㅎㅎ

우선 제 재귀 풀이는 다음과 같습니다.

풀이 1. 재귀 내부에서, 전체 코인에 대한 반복문을 돈다

(vis배열 사용X)

https://www.acmicpc.net/source/89158559
풀이 2. 재귀 내부에서, 중복 조합을 뽑듯이 이전에 사용한 코인을 시작점으로 하여 코인에 대한 반복문을 돈다

(vis배열 사용O)

https://www.acmicpc.net/source/89531232

그리고 제가 헷갈렸던 부분과 그에 대해 스스로 이해한 내용은 다음과 같습니다!

Q. 재귀로 풀 때에 dp의 상태값으로 sum이 충분한 이유

A. sum은 어떤 코인을 사용하느냐에 따라 무작위로 호출되지만, 매개변수에 sum을 포함하며 함수를 매개변수가 k가 될 때까지 전진해나가며 그 sum에 대해 가능한 모든 작은 부분에 대한 재귀(제 코드 로직상 sum+1 부터 k 를 만드는 가능한 재귀)가 호출되기 때문에 다른 상태값이 아닌 sum 하나로 dp를 처리할 수 있는것이다.

다만, dp의 개념 상 자신보다 작은 부분합에 대한 함수를 호출하는 것이 더 직관적으로 와닿기 때문에, 함수를 호출할때 매개변수를 0으로 호출하는 것 보다 k 로 호출하는 것이 논리와 잘 맞는다.( 현재 sum을 만들 때 필요한 최소 동전개수를 받아와서 sum에서 사용한다고 직관적인 이해 가능.

https://www.acmicpc.net/source/89531844

이 풀이처럼 풀이1 의 코드에서 함수 호출과 기저조건을 반대로 바꾼 것을 의미함)

Q. vis배열을 사용하지 않는것과 사용하는 것이 둘 다 맞다고 통과되는 이유는?

A. vis 배열을 사용하지 않으면 말그대로 중복 순열을 구하는 것 같이 보이지만 사실 개수가 아닌 sum을 기준(기저조건)으로 함수를 return해주고 있기때문에, 코인을 넣는 순서에 따라 (큰 코인을 먼저 사용하면 필요한 코인 개수가 더 줄어들 수 있음) 사실 조합의 관점으로 봐도 다른 조합이 만들어진다. (순서만 바뀐 같은 조합이 만들어지는 경우도 있긴 하다)

vis 배열을 사용하면 위에서 "순서만 바뀐 같은 조합이 만들어지는 경우" 를 제외시키고 (ex.112 211과 같은 경우) 서로 다른 중복조합을 만드는 것이기 때문에 vis배열을 사용하지 않는 것 보다 조금 더 효율적이다.

그치만 결과는 둘다 같게 나온다.

이렇게 2개의 질문에 대해 제가 이해한 내용이 맞을까요? 감사합니다!