[Silver IV] 사탕 - 1812

문제 링크

성능 요약

메모리: 110708 KB, 시간: 784 ms

분류

수학, 브루트포스 알고리즘

제출 일자

2026년 04월 25일 22:04:59

문제 설명

N(3≤N≤999, N은 홀수)명의 학생들이 원 모양으로 둘러앉아 있다. 각 학생들은 모두 몇 개의 사탕(≤100,000)을 가지고 있는데 그 개수는 사람마다 다를 수 있고, 사탕을 아예 가지고 있지 않을 수도 있다. 물론 사탕의 개수는 음이 아닌 정수이다.

편의상 학생들에게 번호를 매기는데, 반시계 방향으로 1번 학생, 2번 학생, …, N번 학생으로 번호를 매겼다. 1번 학생 오른쪽엔 2번 학생, 2번 학생 오른쪽엔 3번 학생이 앉아 있는 것이고, 마지막 N번 학생 오른쪽엔 1번 학생이 앉아 있게 된다.

우리는 인접한 두 학생이 가지고 있는 사탕의 수의 합을 안다. 즉 1번 학생과 2번 학생이 가지고 있는 사탕의 수의 합, 2번 학생과 3번 학생이 가지고 있는 사탕의 수의 합, …, N-1번 학생과 N번 학생이 가지고 있는 사탕의 수의 합, 마지막으로 N번 학생과 1번 학생의 가지고 있는 사탕의 수의 합을 안다. 이때, 각 학생이 가지고 있는 사탕의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(3 ≤ N ≤ 999, N은 홀수)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 1번 학생과 2번 학생이 가지고 있는 사탕의 수의 합, 2번 학생과 3번 학생이 가지고 있는 사탕의 수의 합, …, N-1번 학생과 N번 학생이 가지고 있는 사탕의 수의 합, 마지막으로 N번 학생과 1번 학생의 가지고 있는 사탕의 수의 합이 순서대로 주어진다.

출력

첫째 줄부터 N개의 줄에 걸쳐 1번 학생이 가지고 있는 사탕의 수, 2번 학생이 가지고 있는 사탕의 수, …, N번 학생이 가지고 있는 사탕의 수를 순서대로 출력한다. 출력하는 수는 음이 아닌 정수들이어야 하며, 항상 답이 존재하는 경우만이 입력으로 주어진다고 가정해도 좋다.

---

💡 해결 방법

💻 코드

 
# 대전과학고등학교에는 선착순으로 자습 좌석을 신청하는 시스템이 있다.
 
# 대전과학고등학교 학생은 총 $X$명이며, 각 학생의 학번은 $1$ 이상 $X$ 이하의 서로 다른 정수이다. 각 학생은 $C$개의 좌석 중 하나를 골라 신청할 수 있으며, 각 좌석에는 $1$ 이상 $C$ 이하의 서로 다른 정수 번호가 붙어 있다.
 
# 해당 시스템은 다음과 같이 작동한다.
 
# 각 좌석에는 $1$ 이상 $C$ 이하의 서로 다른 정수 번호가 붙어 있다. 각 좌석은 신청된 좌석 또는 신청되지 않은 좌석 중 하나의 상태를 가지며, 학생들이 좌석을 신청하기 전에 모든 좌석은 신청되지 않은 좌석인 상태이다.
# 만약 학생이 신청한 좌석이 이미 누군가에 의해 신청된 좌석이라면 해당 신청은 무효가 된다. 무효가 되지 않은 신청은 성공한 신청이다.
# 좌석 신청에 성공한 학생은 즉시 신청한 좌석에 배정되며, 학생이 신청한 좌석은 신청된 좌석이 된다.
# 만약 이미 좌석을 배정받은 학생이 다른 좌석 신청에 성공한 경우, 기존에 학생이 배정받았던 좌석은 신청된 좌석에서 신청되지 않은 좌석으로 돌아간다.
# 하지만 안타깝게도 시스템이 고장이 나는 바람에 좌석 신청이 제대로 되지 않았다. 다행히 서버에는 학생들이 좌석을 신청한 로그가 남아 있다. 각 로그는 학생이 좌석을 신청한 시각 $T$, 학생이 신청한 좌석 번호 $S$, 그리고 학생의 학번 $N$으로 이루어져 있다. $T$가 작을수록 먼저 일어난 신청이다.
 
# 여러분은 서버에 남아 있는 로그를 기반으로 최종 신청 결과를 복구하려고 한다. 좌석 신청 로그와 학생 수가 주어질 때, 최종적으로 배정받은 좌석 번호를 출력하는 프로그램을 작성하시오.
 
# 입력
# 첫 번째 줄에는 학생 수 $X$와 좌석의 개수 $C$, 로그의 개수 $K$가 공백으로 구분되어 주어진다. $(1 \leq X, C, K \leq 100 \, 000)$ 
 
# 다음 $K$개의 줄에는 학생이 좌석을 신청한 시각 $T$, 학생이 신청한 좌석 번호 $S$, 그리고 학생의 학번 $N$이 공백으로 구분되어 주어진다. $(0 \leq T \leq 1 \, 000 \, 000 \, 000;$ $1 \leq S \leq C;$ $1 \leq N \leq X)$ 
 
# 모든 로그의 신청 시각 $T$는 서로 다르다. 로그는 시각 순으로 정렬이 되어 있지 않을 수도 있다.
 
# 출력
# 각 줄에 학번의 오름차순으로 각 학생의 학번과 배정받은 좌석 번호를 공백으로 구분하여 출력한다. 단, 좌석을 신청하지 않았거나, 좌석 신청에 한 번도 성공하지 못한 학생은 출력하지 않는다.
 
# 예제 입력 1 
# 3 4 5
# 2 1 3
# 1 1 2
# 6 4 1
# 4 2 2
# 7 4 1
# 예제 출력 1 
# 1 4
# 2 2
 
 
n = int(input())
 
listadd = list()
 
for i in range(n):
    listadd.append([int(input()) , i, (i + 1) % n])
 
# print(*listadd, sep = '\n')
 
# print(listadd[-1][0])
 
 
list1 = [0 for i in range(n)]
 
for i in range(0, listadd[0][0] + 1):
    list1[0] = i
    for i in range(1, n):
        list1[i] = listadd[i-1][0] - list1[i - 1]
 
    if list1[0] + list1[-1] == listadd[-1][0]:
        # print('yes')
        print(*list1, sep = '\n')