백준, BOJ, 1793번 C++ [CPP]

 

이 문제는 쉬우면서도

출력을 어렵게해서 난이도를 높인 문제라고 볼 수 있다.

unsigned long long의 범위를 넘어서... 이건 문자열로 계산을 했어야했다.

그리고 너무 어이 없는 문제다.. 

0일 때 값이 1이란다..

넣을 수 없는 공간이 없다면 찬 것이라고 보는 것일까..?

2021.05.30

0에 대한 언급이 전혀 없다.

2 * n 즉, 2 * 0이면 타일을 넣을 수 가 없는데..

 

우선 설명을 달라고 하긴 했다.

 

https://www.acmicpc.net/problem/1793

 

---

 

#맞는 풀이를 보자.

#include<iostream>
#include<string> // reverse() 사용
#include<algorithm>

using namespace std;

string BigNumAdd(string a, string b) {
    string ans = "";

    //A가 B보다 길거나 같게 설정
    int lenA = a.length();
    int lenB = b.length();
    string strA = a;
    string strB = b;

    //lenA가 항상 크거나 같음
    if (lenA < lenB) {
        int temp = lenB;
        lenB = lenA;
        lenA = temp;
        strA = b;
        strB = a;
    }



    int gap = lenA - lenB;
    int prev = 0;

    //B와 겹치는 부분 계산 -> 맨끝부터
    for (int i = lenB-1; i >= 0; i--) {
        int a = strA[gap + i] - '0';
        int b = strB[i] - '0';
        int result = a + b + prev;
        ans += to_string((result % 10)); //역순으로 추가
        prev = result / 10;
    }


    //prev == 0이면 a는 그대로 올림.
    if (prev == 0) {
        for (int i = gap - 1; i >= 0; i--) {
            ans += strA[i];
        }
    }
    else {
        //다 돌아도 prev가 1이라면 A의 자리수 올려줘야함
        for (int i = gap - 1; i >= 0; i--) {
                int result = int(strA[i]) + prev;
                ans += to_string((result % 10)); //역순으로 추가
                prev = result / 10;
        }
        

        //그래도 prev = 1이면 마지막에 1추가
        if (prev != 0) {
            ans += "1";
        }
    }
    

    
    //역순으로 추가했으니 다시 역순으로 정렬
    reverse(ans.begin(), ans.end());

    return ans;
}

string dp[260];

int n;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    dp[0] = "1";
    dp[1] = "1";
    dp[2] = "3";
    dp[3] = "5";

    for (int i = 4; i < 251; i++) {
        dp[i] = BigNumAdd(BigNumAdd(dp[i - 2], dp[i - 2]), dp[i - 1]);
    }
    while (cin >> n) {
        cout << dp[n] << "\n";
    }
    
}

 

그리고 테스트 케이스 개수가 주어지지 않을 때 출력을 어떻게 해야할지 살펴보자

나는 1번으로 했지만

#1

    while (cin >> n) {
        cout << dp[n] << "\n";
    }

고수분 들은 2번으로 했단다

#2

    while (1) {
        cin>>n;
        if (cin.eof()==true) {
            break;
        }
        cout << dp[n] << "\n";
    }

 

 

---

 

그리고 문제를 보자...

 

문자열로 계산했어야 했고

다이나믹 프로그래밍으로 풀어야 하는 문제였다.

 

주석도 적어놓았으니

잘 살펴보자

 

가짓수 구할 때는 최소 n=5일 때까지 해보고 이전 항으로 다음 항을 구할 수 있는 지 생각해보자