백준 18323 Photoshoot (USACO January 2020 Bronze 2번)

문제 링크: https://www.acmicpc.net/problem/18323

18323번: Photoshoot

예시 1

5

4 6 7 6

첫수를 1부터 4 - 1 까지 시도해 보면서 가능할때 출력하면 됨.

첫수가 1일때: 1 3 3 (세번째 숫자가 3이 되야 하는데, 두번째 숫자랑 중복이 되므로 안됨)

첫수가 2일때: 2 2 (두번째 숫자와 첫번째 숫자가 중복)

첫수가 3일때: 3 1 5 2 4 (답)

예시 2

6

5 7 8 5 8

첫수가 1일때: 1 4 3 5 0 (다섯번째 숫자가 0이 되야 하는데, 0은 사용할수 없음)

첫수가 2일때: 2 3 4 4 (네번째 숫자와 세번째 숫자가 중복)

첫수가 3일때: 3 2 5 3 (네번째 숫자와 첫번째 숫자가 중복)

첫수가 4일때: 4 1 6 2 3 5 (답)

#include <bits/stdc++.h>
using namespace std;
 
int n, p[1001], ans[1001], check[1001];
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n;
    for(int i = 0; i < n - 1; i++) cin >> p[i];
 
    for(int x = 1; x < p[0]; x++) {
        memset(check, 0, sizeof(check));
        ans[0] = x;
        check[x] = 1;
        bool ok = true;
 
        for(int i = 1; i < n; i++) {
            ans[i] = p[i - 1] - ans[i - 1];
            if(ans[i] <= 0 || check[ans[i]] == 1) {
                ok = false;
                break;
            }
            check[ans[i]] = 1;
        }
 
        if(ok) {
            for(int i = 0; i < n; i++)
                cout << ans[i] << ' ';
            cout << '\n';
            return 0;
        }
    }
    return 0;
}