[BaekJoon] 생각의 전환 feat.2225번(합분해)

 + 이 글은 작성자가 직접 공부하고 복습하며 작성한 글입니다. 만약 직접 작성하지 않았다면, 꼭 출처를 밝히겠습니다!

 + 이 글은 개인적인 공부를 바탕으로 작성되었기에, 틀린 부분이 있을 수 있으며, 틀린 부분이 있다면 알려주시면 감사하겠습니다!

 + 이 글을 다른 곳으로 가져가신다면, 꼭 출처를 남겨주세요~

 + '참고사이트'는 공부하기 위해 참고한 사이트들을 모아 둔 것입니다.

 2225번 문제를 풀지 못해 다른 사람들의 접근방식을 참고했었는데, 그 접근 방식들로 인해 충격을 받았다.

 "와... 저렇게도 볼 수 있구나..."라는 생각에 여기에 기록을 남깁니다.

---

 *** 문제를 보면, 정수 N을 K개의 정수의 합으로 나타낸다고 할 때, 경우의 수를 구해야 한다.

 *** https://www.acmicpc.net/problem/2225

[내 접근 방식](틀림)

0  ─ 0

    └ 0 ─ 0
            └ 0
와 같이 트리형태로 만들어 각 자리에 올 수 있는 경우의 수를 구해 곱한다.

[옳은 접근 방식] (정답)
1. N개의 1을 나열한 뒤, K개의 나무 를 두는 경우의 수를 생각해라
ex) N = 5, K = 3
1 1 1 1 1 & l l l    =>    l 1 l 1 1 1 l 1 or l l l 1 1 1 1 1
와 같은 경우의 수를 구하면 된다.

2. 시작점에서 N까지 K개의 경로로 갈 때, 갈 수 있는 방법의수를 생각해라
ex) N = 4, K = 4

에서 N과 K에 맞는 점까지의 최단 거리 횟수를 구하면 된다.
K 열의 번호를 "1번째 수 + 2번째 수 + 3번째 수 + 4번째 수"로 생각해서, 오른 쪽으로 이동한 횟수 만큼 해당 번째의 수를 표시해주면 된다.

위와 같은 경우라면,
 "1번째 수 + 2번째 수 + 3번째 수 + 4번째 수"  ->  "1 + 2 + 0 + 1"  으로 4가 이루어 진다는 말이다.

최단 거리 횟수를 구하는 이유는, 하나의 K에서 될 수 있는 숫자는 N이 최대이기 때문이다.

---

** 참고사이트 **

 - https://www.acmicpc.net/problem/2225