[Baekjoon/JAVA] 1703번 - 생장점

Baekjoon Online Judge

문제로 이동

 

문제

branchorama 나무는 특이한 규칙을 가지고 성장합니다. 어린 branchorama 초목은 하나의 잎을 꼭대기에 가진 가는 묘목이며, 그 잎에는 생장점이 있습니다. 성장하는 계절 동안 나무의 생장점들은 여러 개의 가지로 나뉘게 되며, 성장이 끝나면 각 가지는 생장점을 가진 하나의 잎을 꼭대기에 매달게 됩니다. 놀랍게도 같은 나무의 모든 생장점들은 같은 숫자(splitting factor)의 가지로 나뉘며, 그 숫자는 해가 지남에 따라 변합니다.

아래의 예는 Brown 씨의 과수원에서 한 branchorama 나무가 유목에서부터 3년간 자란 결과를 보여줍니다.

예시에서 예측할 수 있듯이, branchorama 나무는 과밀하게 성장하는 경향이 있습니다. 따라서 Brown 씨는 매 겨울마다 과도하게 성장한 나무들의 가지를 쳐냅니다. 아래는 가지를 쳐낸  branchorama 나무의 예입니다

branchorama 나뭇잎은 굉장히 크고 광합성에 유리하지만, 오직 생장점이 온전히 보존된 가지의 끝에만 달립니다. 따라서 나무가 버티지 못할 정도로 가지를 쳐내는 일은 없어야 합니다.

Brown 씨는 각 나무가 몇 개의 잎을 가졌는지 알고 싶어합니다. 나뭇잎을 일일이 세는 것은 지루하기 때문에, 각 해(level) 성장기의 splitting factor와 그 해 겨울에 쳐낸 가지의 수를 이용해 Brown 씨에게 나뭇잎의 수를 알려주세요.

 

입력

입력의 각 줄은 하나의 branchorama 나무를 의미합니다.

각 줄은 나무의 나이 a(1 ≤ a ≤ 20)로 시작하며, 그 뒤로 2a 개의 정수가 공백을 두고 주어집니다. 2a 개의 정수는 splitting factor와 가지치기 한 가지의 수가 level 별로 나열된 것입니다.

마지막 줄로  '0'이 주어지며 더 이상의 입력은 없습니다. '0'은 처리하지 않습니다.

 

출력

각 나무에 대하여 나무에 달려있는 잎의 수를 한 줄씩 출력하세요. 나뭇잎의 수가 signed 32-bit integer를 초과하지 않는다고 가정해도 좋습니다.

 

---

예제 입력	예제 출력
1 3 0 2 3 0 2 0 3 3 0 2 0 2 0 3 3 0 2 1 2 3 2 4 1 3 4 4 5 0 5 1 5 2 5 101 0	3 6 12 7 5 489

---

풀이

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        while (true) {
            int a = in.nextInt(); // 나무의 나이
            int leaf = 1; // 나뭇잎의 수

            if (a == 0) break;

            for (int i = 0; i < a; i++) {
                int sF = in.nextInt(); // splitting factor
                int cut = in.nextInt(); // 가지치기 한 가지의 수

                leaf = leaf * sF - cut;
            }

            // 출력
            System.out.println(leaf);
        }
    }
}

예제 3번째 줄로 어떻게 문제를 풀었는지 설명하겠다.

3 3 0 2 0 2 0

예제 3번째 줄의 입력은 위와 같다. 가장 첫 번째 숫자는 나무의 나이이며, 그 뒤의 숫자는 splitting factor와 가지치기 한 가지의 수이다. 나는 이 수열을 처음 보고 가지가 새로 3개씩 나고 중간중간 가지를 2개씩 2번 잘라 총 가지를 4개 자른 줄 알았다. 하지만 이러면 나무의 나이와 맞지 않아 무척 고민했다. 결론을 말하자면 저 수열은 나무의 나이를 보여주는 첫 번째 숫자를 제외한 숫자들은 2개씩 짝지어서 생각해야 하는 것이었다.

년   1    2    3
3 |3 0 |2 0 |2 0

위처럼 첫 번째 해에 splitting factor이 3개, 가지치기는 0개, 두 번째 해에 splitting factor이 2개, 가지치기는 0개 이렇게 보면 되는 것이다.

 

            int leaf = 1; // 나뭇잎의 수

            for (int i = 0; i < a; i++) {
                int sF = in.nextInt(); // splitting factor
                int cut = in.nextInt(); // 가지치기 한 가지의 수

                leaf = leaf * sF - cut;
            }

입력한 숫자들의 정체를 알아낸 후 for문으로 각 해마다 나무에 달려있는 잎의 수를 계산한 뒤 값을 출력했다. 나무는 처음에 나뭇잎이 1개이므로 leaf 변수를 1로 초기화했다.