Baekjoon 15988 1, 2, 3 더하기 3 JAVA

이 문제는 예전에 풀었던 9095 1, 2, 3 더하기를 활용하여 쉽게 해결하였다.

https://blog.naver.com/soonil0119/222216120251

Baekjoon 9095 1, 2, 3 더하기 JAVA

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

15988번: 1, 2, 3 더하기 3

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%2015988

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

 

문제는 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하는 것이다.

정수 n은 11보다 작으며, 4의 경우 2+1+1과 1+2+1, 1+1+2는 각각 한 가지 방법으로 친다.

​

처음에 문제를 보고 공책에 1부터 5까지 경우의 수를 모두 써보면서 규칙을 파악했으나 뭔가 규칙이 애매한 거 같아서 결국 6의 경우까지 나열해 보다 보니 규칙을 파악하게 되었다.

위의 그림을 보면 1부터 6가지 모든 경우의 수를 나타냈으며 4의 경우 3의 경우와 2의 경우, 1의 경우의 합과 같은 걸 볼 수 있고, 5의 경우는 4의 경우와 3의 경우 2의 경우와 같은 걸 볼 수 있다 이를 이용해 코드를 작성하였고 정수 n의 범위가 크므로 long을 이용하여 배열을 할당해 주고 이후 합을 1,000,000,009로 나누어 저장해주면 쉽게 해결 가능하다.