[C++] 백준 1560번:비숍(stack)

문제링크

1560번: 비숍

문제

세준이는 따분해진 나머지 갑자기 체스 판의 크기를 마음대로 조정하는 체스 판을 만들었다.

세준이는 N*N 크기의 체스 판에 과연 몇 개의 비숍 (BISHOP)을 세울 수 있는지 궁금해 졌다.

비숍 (BISHOP)은 자신의 위치에서 대각선 왼쪽 위, 대각선 왼쪽 아래, 대각선 오른쪽 위, 대각선 오른쪽 아래 () 이렇게 4방향으로 움직일 수 있는 말이다.

체스판의 크기가 주어졌을 때, 서로 잡아먹지 않게 최대로 비숍을 몇 개를 놓을 수 있는지 구하는 프로그램을 작성하시오.

입력

체스판의 크기 N이 주어진다. N은 10진수로 70자리 이하인 자연수이다.

출력

최대로 비숍을 몇 개 놓을 수 있는지 출력한다.

 

풀이

문제 풀이는 굉장히 쉽다. 직접 그림을 그려보면 n이 1일 때를 제외하고는 n + n - 2가 정답인 것을 금방 알 수 있다.

파이썬이나 자바로는 위의 내용을 그대로 적어 제출하면 되지만 c++에서는 그렇지 않다. N은 10진수로 70자리 이하인 자연수이다. 라는 조건 때문이다.

long long의 자료형을 사용해도 70자리는 택도 없기 때문에 string으로 구현해야 한다. 때문에 코드가 복잡하다..

실제로 c++로 제출한 사람들을 보면 많이 틀렸고, 맞은 사람도 많지 않았다. 아마 위의 조건을 인식하지 못하지 않았을까 생각한다.

코드

#include <iostream>
#include <stack>
using namespace std;
 
string n;
stack<int> s;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    if (n == "1" || n == "2") {
        cout << n;
    }
    else {
        int size = n.size();
 
        // 숫자로 변환
        for (int i = 0; i < size; i++) {
            n[i] = n[i] - '0';
        }
 
        // 올림 flag
        bool up = false;
        for (int i = size - 1; i >= 0; i--) {
            if (n[i] * 2 >= 10) {
                n[i] = n[i] * 2 - 10;
                if (up == true) {
                    n[i]++;
                    up = false;
                }
                up = true;
                s.push(n[i]);
            }
            else {
                n[i] = n[i] * 2;
                if (up == true) {
                    n[i]++;
                    up = false;
                }
                s.push(n[i]);
            }
        }
        // 올림수 추가 (ex 5 -> 10)
        if (up == true) {
            s.push(1);
        }
 
        size = s.size();
        for (int i = 0; i < size - 2; i++) {
            cout << s.top();
            s.pop();
        }
 
        // n-2계산
        if (size >= 2) {
            int fir = s.top();
            s.pop();
            int sec = s.top();
            int last = fir * 10 + sec;
 
            // last-2<10 : 55.. 처리 위함
            // size>2 : 5 처리 위함
            if (last - 2 < 10 && size > 2) {
                cout << 0 << last - 2;
            }
            else {
                cout << last - 2;
            }
        }
        else {
            cout << s.top() - 2;
        }
    }
 
}

 

메모

c++의 한계..라고 해야 하나 다른 언어의 장점이라고 해야하나.. 다른 언어도 어렵지 않을 정도로 구현이 가능하면 풀이 능력이 훨씬 좋아질 것 같다는 생각을 했다.