본문으로 바로가기

[백준 9095] 1, 2, 3 더하기

category 알고리즘/백준 알고리즘 2018. 4. 20. 11:12
글에 개요

백준 알고리즘 9095번 "1, 2, 3 더하기" 문제입니다.
이 문제는 DP(동적 계획법)을 활용하는 문제로 팰린드롬에 이어 2번째 등장이네요.
아마 동적 계획법에 사용되는 점화식의 활용에 익숙해지고, 이후 재귀함수로 구현할 때 Top-down, Bottom-up 방식해 질 때까지 최대한 꾸준히 풀어볼 생각입니다.

[백준 9095] 1, 2, 3 더하기https://www.acmicpc.net/problem/9095

참고할 글
  1. [백준 10942] 팰린드롬? http://brenden.tistory.com/27
핵심 내용
  1. 정수 n을 1,2,3의 조합으로 나타내는 방법의 수를 구하는 문제입니다.
  2. D[i] = i를 1,2,3의 조합으로 나타내는 방법의 수
  3. D[i] = D[i-1] + D[i-2] + D[i-3]
  4. 위 점화식을 활용하여 문제를 해결할 것입니다.


해결 방법
  1. n이 11보다 작은수라고 정해져 있기 때문에 크기가 11인 배열을 만들어줍니다.
  2. answerAry[0] = 1로 초기화
  3. 위의 점화식으로 해결할 때, 현재 index값이 3이 넘어가기 전까지는 1의 조합 혹은 2의 조합만 가능하기 때문에 이에 대한 예외처리를 해줍니다.
해결한 코드



백준 내용 참고

시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초128 MB150979927690964.162%

문제

정수 4를 1, 2, 3의 조합으로 나타내는 방법은 총 7가지가 있다.

  • 1+1+1+1
  • 1+1+2
  • 1+2+1
  • 2+1+1
  • 2+2
  • 1+3
  • 3+1

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

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력

각 테스트 케이스마다, n을 1,2,3의 합으로 나타내는 방법의 수를 출력한다.

예제 입력 1 

3
4
7
10

예제 출력 1 

7
44
274






댓글을 달아 주세요