백준 17520번 Balanced String

🔒문제 url

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

🪄전체 코드

#include <iostream>

using namespace std;
#define IAMFAST ios_base::sync_with_stdio(false);cin.tie(0);

int n;

void INPUT()
{
    IAMFAST
    cin >> n;
}

void solution()
{
    /*
     * n이 홀수인 경우, 0과 1의 갯수 차이는 반드시 1이어야 한다.
     * n이 짝수인 경우, 0과 1의 갯수는 반드시 동일해야 한다.
     *
     * 이는 n이 홀수에서 짝수로 넘어가는 경우 균형잡인 문자열의 수는 동일함을 의미한다.
     * (갯수 차이가 1에서 동일해져야 하므로 뒤에 붙는 수가 고정되어야 한다.)
     * 짝수에서 홀수로 넘어가는 경우, 균형잡인 문자열의 수는 2배가 된다.
     * (갯수가 동일한 상태이므로, 뒤에 0이 붙든 1이 붙든 갯수 차이가 1임이 보장된다.)
     *
     * 즉,
     * n = 1 or n = 2 => 2
     * n = 3 or n = 4 => 4
     * n = 5 or n = 6 => 8
     * 형태가 반복되므로, 2^((n+1)/2)승이 출력 답안이 된다.
     */

    int ans = 1;
    for (int i = 0; i < (n+1)/2; i++) ans *= 2, ans %= 16769023;
    cout << ans;
}

int main()
{
    INPUT();
    solution();
}

🥇문제 후기

GOLD5 미만 난이도는 알고리즘 및 풀이 설명을 주석으로 대체합니다.
주석을 참고해주세요.