BaekJoon 9095번: 1, 2, 3 더하기

풀이법

1) n의 수가 작기에 for문을 이용하거나 다른 방식을 써도 좋지만 확장성을 고려한다면 DP로 푸는 것이 중요하다.

2) 점화식을 구현한다면 누구나 쉽게 풀 수 있는 문제라고 생각한다.

   예시에 있는 4의 경우

    1+1+1+1 / 1+2+1 / 2+1+1 / 3+1

    1+1+2/ 2+2

    1+3

    형태를 띄는 것을 알 수 있다.

    끝이 1로 끝나는 경우 3을 1, 2, 3의 합으로 나타내는 방법의 개수와 같고,

    끝이 2로 끝나는 경우 2를 1, 2, 3의 합으로 나타내는 방법의 개수와 같고,

    끝이 3으로 끝나는 경우 1을 1, 2, 3의 합으로 나타내는 방법의 개수와 같다.

    최종 점화식은 D[i]=D[i-1]+D[i-2]+D[i-3] 이 될 것이다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <cstring>
using namespace std;

int n;
int arr[12];
void dp(int a)
{
	arr[1] = 1;
	arr[2] = 2;
	arr[3] = 4;
	for (int i = 4; i <= a; i++)
	{
		arr[i] = arr[i - 1] + arr[i - 2] + arr[i - 3];
	}
	cout << arr[a] << "\n";
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		memset(arr, 0, sizeof(arr));
		dp(a);
	}
}

한계점 및 개선사항 (+주의사항)

매번 배열을 초기화 시켜서 Test case 마다 잘 출력하기 위해서는 memset을 이용하면 된다.

 

github.com/pearlcrum/CodingTest/tree/main

pearlcrum/CodingTest