[백준 알고리즘][파이썬/Python] 1812번: 사탕

문제

시간 제한 : 2초, 메모리 제한 : 128 MB

 

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번 학생이 가지고 있는 사탕의 수를 순서대로 출력한다. 출력하는 수는 음이 아닌 정수들이어야 하며, 항상 답이 존재하는 경우만이 입력으로 주어진다고 가정해도 좋다.

 

입출력 예

 

제출 코드

import sys
n = int(input())
lst = [int(sys.stdin.readline()) for i in range(n)]
result = []
first = 0

for idx, val in enumerate(lst):
    if idx % 2 == 0:
        first += val
    else:
        first -= val
result.append(first//2)

for i in range(n-1):
    result.append(lst[i]-result[i])

for i in result:
    print(i)

문제의 핵심

# 1

학생의 수가 홀수라는 것을 인지해야 한다. 이는 나중에 연립방정식을 이용할 때 중요한 단서가 된다.

 

# 2

학생들이 가지고 있는 사탕의 수는 (1번 학생 + 2번 학생), (2번 학생 + 3번 학생) 과 같은 식으로 주어진다. 그렇기 때문에 몇 번째 학생이든 한 학생이 몇 개의 사탕을 정확히 가지고 있는지만 알면 나머지 학생들이 가지고 있는 사탕의 개수는 모두 파악할 수 있다.

 

라인 별 풀이

(1) line 3

학생의 수 N 다음의 입력값을 리스트에 저장한다. 이 리스트는 나중에 연립방정식에 이용된다.

 

(2) line 4

각 학생이 몇 개의 사탕을 가지고 있는지 저장하기 위한 리스트 result를 선언한다.

 

(3) line 5

본인은 1번 학생의 숫자를 파악하는게 가장 편하다고 생각했다. 그래서 1번 학생이 가지고 있는 사탕의 개수를 저장하기 위해 first라는 변수를 선언한다.

 

(4) line 7 ~ 12

이 문제를 풀기 위한 핵심 로직이다. 이 코드에 대한 설명은 예시를 들어서 설명하는 것이 훨씬 쉬울 것 같다.

 

문제에서 주어진 입출력 예제는 총 3명이다. 각 학생이 가지고 있는 사탕의 개수를 a, b, c라고 했을 때 a를 구하는 과정은 다음과 같다.

+ (a + b)

-  (b + c)

+ (c + a)

----------

=        2a

 

문제를 통해 확인할 수 있는 값은 (a+b), (b+c), (c+a) 와 같은 형태라 그것을 이용해야 하는데 구하고자 하는 a 이외의 변수들을 모두 소거하려면 위와 같은 방식으로 처리해주면 된다. 만약 입력값이 5여도 마찬가지다.

+ (a + b)

-  (b + c)

+ (c + d)

-  (d + e)

+ (e + a)

----------

=       2a

 

이와 같은 과정을 통해 얻어낸 2a라는 값에서 2를 나눠주고 그 값을 리스트 result에 append한다. 이제 1번 학생이 정확히 몇 개의 사탕을 가지고 있는지 파악했다.

 

(5) line 14, 15

1번 학생을 제외하고 2번 학생부터 N번 학생까지 순회하며 그들이 정확히 몇 개의 사탕을 가지고 있는지 result에 저장해주는 과정이다. 위 과정을 통해 result에는 아래와 같은 값들이 저장된다.

 

result[1] = (a + b) - a   # 2번 학생이 가진 사탕의 개수

result[2] = (b + c) - b   # 3번 학생이 가진 사탕의 개수

result[3] = (c + d) - c   # 4번 학생이 가진 사탕의 개수

...

result[N-1] = # N번 학생이 가진 사탕의 개수

 

(6) line 17, 18

각 학생이 가진 사탕의 개수를 순회하며 그것을 출력해준다.

 

 

 

Source : https://www.acmicpc.net/problem/1812