BOJ 다이나믹 프로그래밍 알고리즘 풀이
9095번 - 1, 2, 3 더하기
주어진 정수 N을 1, 2, 3의 합으로 나타낼 수 있는 방법의 수 구하기. (N < 11, N = 양수)
규칙
- 1, 2, 3을 더해서 주어진 정수가 되게 만들면 된다.
다음은 해당 문제에 대한 예시.
해결
- N > 3인 경우는 항상 1, 2, 3으로 한 자리를 고정할 수 있다.
- 주어진 정수가 N이고, 마지막 자리에 올 수 있는 숫자를 1, 2, 3으로 가정하면 1은 N-1, 2는 N-2, 3은 N-3이 된다.
마지막 자리 수를 뺀 나머지를 만들 수 있는 경우의 수를 다 더하면 N의 총 경우의 수가 된다. (아래 이미지 참고)
풀이한 코드
올 수 있는 숫자가 제한 되어 있기 때문에 금방 풀 수 있었다.