[코드트리] 초기 수열 복원하기

https://www.codetree.ai/missions/5/problems/restore-initial-sequence?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

이건 너무 무식하게 풀려고 해서 ,, 해설을 참조하였다.

첫 숫자가 정해지면 뒤로 주르륵 숫자가 정해지니 전부 1번씩 사용했는지만 체크해주면 된다!

 

#include <iostream>
using namespace std;
int n, map[1000], answer[1000];
int main() {
    cin >> n;
    for(int i=0; i<n; i++)  
        cin >> map[i];

    // 첫 숫자 정하기
    for(int i=1; i<=n; i++){
        answer[0] = i;
        int dat[1001] = {0, }, flag = 0;
        dat[i] = 1;
        for(int j=0; j<n-1; j++){
            answer[j+1] = map[j] - answer[j];
            if(answer[j+1] < 0 || answer[j+1] > n) break;
            dat[answer[j+1]]++;
        }

        for(int j=1; j<=n; j++){
            if(dat[j] != 1) flag = 1;
        }
        if(flag == 0){
            for(int j=0; j<n; j++)
                cout << answer[j] << ' ';
            return 0;
        }
    }
    return 0;
}