Baekjoon 9095 1, 2, 3 더하기 JAVA

해당 문제는 DP를 사용하여 해결하였으며 답을 적어보다가 특정 규칙을 발견하여 쉽게 해결한 문제이다.

​

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

9095번: 1, 2, 3 더하기

 

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

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의 경우와 같은 걸 볼 수 있다 이를 이용해 코드를 작성하였고 해당 문제를 간단히 해결할 수 있었다.