[Jungol] 정올 2601 종이접기

출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1862&sca=50  

Approach

주어지는 접는 횟수 n에 대해서 출력되는 모양 규칙을 파악해야 한다.

(n = 1) ∨

(n = 2) ∧∨∨

(n = 3) ∧∧∨∨∧∨∨

(n = 4) ∧∧∨∧∧∨∨∨∧∧∨∨∧∨∨

 

현재 문자열의 길이 = len 일 때,

n이 증가할 때 다음 문자열의 길이는 {2 × len + 1} 이다.

 

이때, 기존 문자열에서 중간 '∨'이 삽입되고

중간을 기준으로 뒤쪽에 있는 글자가 뒤집혀서 앞쪽에 배치되는 형태 입니다.

* 설명을 위해서 문자 변경

                            v

                        ^vv

                ^^vv^vv

^^v^^vvv^^vv^vv

n이 증가할 때, 기존 문자열 구성과 길이를 이용해서

앞에 붙여지는 문자열을 누적해서 구성할 수 있다.

문제 조건상에서 (n ≤ 20) 이기 때문에 문자열의 최대 길이는 1,048,575 이다.

---

#include <stdio.h>
char str[1048575 + 5];

int main()
{
    // freopen("input.txt", "r", stdin);
    int n;
    scanf("%d", &n);
    str[0] = 'v';
    int len = 1;
    for (int i = 2; i <= n; ++i)
    {
        str[len] = 'v';
        
        int end = len; // before
        len = 2 * len + 1;
        int start = len; // after
        int tg = 0;
        for (int j = start - 1; j > end; j--)
        {
            if (str[tg] == '^')
                str[j] = 'v';
            else
                str[j] = '^';
            tg++;
        }
    }
    for (int i = len - 1; i >= 0; i--)
    {
        if (str[i] == '^')
            printf("∧");
        else
            printf("∨");
    }
    printf("\n");
}