PS/BOJ
[백준] 9095.cpp : 1, 2, 3 더하기
bconfiden2
2020. 7. 1. 20:50
9095번: 1, 2, 3 더하기
문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는
www.acmicpc.net
#include <iostream>
using namespace std;
int main(void)
{
// 1, 2, 3 일때 각각의 갯수 담아놓음
int answer[11] = {0, 1, 2, 4};
// 4 이상부터는 [(i-3) 에 3을 더하는 방법]. [(i-2) 에 2를 더하는 방법], [(i-1) 에 1을 더하는 방법] 의 합으로 구할 수 있다.
for(int i = 4 ; i < 11 ; i++)
{
answer[i] = answer[i - 1] + answer[i - 2] + answer[i - 3];
}
int t;
cin >> t;
for(int tc = 0 ; tc < t ; tc++)
{
int n;
cin >> n;
cout << answer[n] << '\n';
}
}
[Approach]
1. 재귀 처럼 DP 배열 만들어놓고 규칙에 의해 구하면 될 것 같다.
[Point]
1. 문제에서 n 의 범위를 왜 10까지밖에 안줬을까? 그냥 배열 10개 직접 구해서 계산해도 맞다.
2. 생각보다 1,2,3 의 순서도 영향을 미친다는 점 때문에 살짝 헷갈렸다.