[백준 1812] 사탕 (자바)

백준 1812번: 사탕

문제 설명

N명의 아이들이 동그랗게 앉아 있습니다. 각 아이들은 사탕을 받고, 각 아이가 받은 사탕의 개수를 말합니다. N명의 아이들이 받은 사탕의 개수를 바탕으로 각 아이가 몇 개의 사탕을 받았는지 정확히 계산해야 합니다. 주어진 값으로부터 각 아이가 받은 사탕의 수를 구하는 문제입니다.

문제 접근 방법

1. N명의 아이들이 받은 사탕의 수를 입력받아 배열에 저장합니다.
2. 배열의 각 원소는 이전 아이와 다음 아이의 사탕 개수의 합으로 주어집니다.
3. 이를 바탕으로 첫 번째 아이가 받은 사탕의 개수를 계산합니다.
4. 첫 번째 아이의 사탕 개수를 바탕으로 나머지 아이들의 사탕 개수를 순차적으로 계산합니다.

시간 복잡도 분석

O(N)

이 문제는 N명의 아이들에 대해 각 아이가 받은 사탕의 개수를 한 번씩 계산하는 단순한 반복문을 사용합니다. 따라서 시간 복잡도는 O(N)입니다.

해결 방법

아래는 주어진 사탕의 개수를 계산하는 Java 코드입니다:

package re_01;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ_1812_사탕 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] input = new int[N + 1];
        for (int i = 1; i < N + 1; i++) {
            input[i] = Integer.parseInt(br.readLine());
        }

        int[] answers = new int[N + 1];
        int sum = 0;
        for (int i = 1; i < input.length; i++) {
            if (i % 2 == 0) {
                sum -= input[i];
            } else {
                sum += input[i];
            }
        }
        answers[1] = sum / 2;
        for (int i = 2; i < input.length; i++) {
            answers[i] = input[i - 1] - answers[i - 1];
        }

        for (int i = 1; i < N + 1; i++) {
            System.out.println(answers[i]);
        }
    }
}