BOJ 9095 - 1, 2, 3 더하기 (C++)

ps 재활일기 그 두 번째 날

Class 3 탈환을 위해 푼 문제이다

처음에 보고 든 생각이 백트래킹이나 dp겠다...~~ 였음 그 이유는... 결국 일일히 다 1 2 3 연산을 돌려봐야 답이 나오는 문제일 거라고 생각했고 그걸 좀 효율적으로 할 수 있는 게 위 두 방법이기 때문에

근데 dp로 품 이유는 시간제한 1초(추가 시간 없음)이 뭔가뭔가 쎄해서...ㅋㅋㅋㅋㅋ 숫자가 커도 10이긴 한데 그래도 뭔가뭔가 쎄했음ㅋㅋㅋ (그리고 재귀 더럽게 못 짬 이건... 노력해야되는 부분이긴 한데..ㅋ 아무튼)

나는 2차원 배열로 문제를 풀었음

그림으로 그리자면 이렇게~

행이 합 구한 숫자고, 열이 그 숫자를 구하기 위해 전에서 더한 숫자를 의미함 매우매우.. 간단

코드는 여기~

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> arr(13, vector<int>(4, 0));	//9일 때 +1해야 10일 때 완전한 결과를 얻으니까 9+3 = 12행까지는 할당해둠

void makeArr() {
    arr[1][1] = 1;
    arr[2][2] = 1;
    arr[3][3] = 1;	//얘네는 고정해주고 1부터 루프 돌림
    for (int i = 1; i <= 9; i++) {
        int sum = arr[i][1] + arr[i][2] + arr[i][3];
        arr[i+1][1] = sum;
        arr[i+2][2] = sum;
        arr[i+3][3] = sum;

    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int t, n;
    cin >> t;
    makeArr();
    
    while (t--) {
      cin >> n;
      cout << arr[n][1] + arr[n][2] + arr[n][3] <<'\n';
    }
}

이렇게 또 한 문제 날먹을 완료...
1차원 배열로도 구현할 수 있는 것 같더라.. (사실 그게 나을 지도) 그럴 때는 1, 2, 3 일 때 각각 1 2 4 할당해 두고 4에서 부터 123 234 456 이런 식으로 더해주면서 가면 됨... 사실 이게 더 간단한데 내가 괜히 귀찮게 푼 거 같기도 하고 싶다ㅋㅋㅋ 뭐.. 복잡한 거 구현하는 연습 했다고 치지 뭐~

아무튼 오늘도 이렇게 끝~