Kolakoski sequence

문제 >

(1), (2, 2), (1, 1), (2) 네개의 패턴만으로 이루어진 sequence 이다.

초기 sequence는 1, 2, 2 로 설정

i 번째 반복 에서 시퀀스의 i 번째 값 으로 이미 출력된 x(i) 값을 읽는 알고리즘

i>=3일때, i 가 홀수이면 숫자 1의 x(i) 개 복사본을 출력하고 i 가 짝수이면 숫자 2의 x(i) 개를 출력한다.

 

x(i) 는 sequence에서 빨간색으로, 추가된 sequence에는 파란색으로 표기하였다.

i	x(i)	sequence
1	1	1
2	2	1, 2, 2
3	2	1, 2, 2, 1, 1
4	1	1, 2, 2, 1, 1, 2
5	1	1, 2, 2, 1, 1, 2, 1
6	2	1, 2, 2, 1, 1, 2, 1, 2, 2

 

입력 >

테스트케이스 입력값이 주어진 후 테스트케이스 갯수만큼의 i 의 값이 주어진다. 

 

출력 > 

입력받은 i 번째에 해당하는 x(i)값을 출력한다.

 

입출력 예시 >

입력	출력
4 3 7 9 25	2 1 2 1

 

---

 

int kolakoski (int n){
    int map[1001];
    fill_n(map, 1000, 0);
    map[0] = 1;
    map[1] = 2;
    map[2] = 2;
    int pattern = 3;
    int end = 3; //배열의 현재길이
    //end>=n이 되어버리면 map[n-1]의 값이 나오게됨
    while(end<n && n>3){
        if (pattern%2==0){ //짝수
            int x = map[pattern-1];
            for(int j=0;j<x;j++){
                map[end] = 2;
                end++;
            }
        }else { //홀수
            int x = map[pattern-1];
            for(int j=0;j<x;j++){
                map[end] = 1;
                end ++;
            }
        }
        pattern++;
    }
    return map[n-1];
}

어렵진않았다.

그러나 힘들었다.