-
이 문제는 예전에 풀었던 9095 1, 2, 3 더하기를 활용하여 쉽게 해결하였다.
https://blog.naver.com/soonil0119/222216120251
https://www.acmicpc.net/problem/15988
https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%2015988
문제는 정수 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로 나누어 저장해주면 쉽게 해결 가능하다.
728x90'알고리즘 > Baekjoon' 카테고리의 다른 글
Baekjoon 11052 카드 구매하기 JAVA (0) 2021.11.06 Baekjoon 2667 단지번호붙이기 JAVA (0) 2021.11.06 Baekjoon 1012 유기농 배추 JAVA (0) 2021.11.05 Baekjoon 2606 바이러스 JAVA (0) 2021.11.05 Baekjoon 11047 동전 0 JAVA (0) 2021.11.05 댓글