행복한 사람

WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED! 

ssh 접속시 WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!가 발생할 때가 있다.

1) 문제

• https://www.acmicpc.net/problem/1991
• 이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

2) 풀이

 -  inorder, preorder, postorder 구현.

3) 코딩

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

public class BOJ_1991_트리_순회 {
    static final int MAX_NODE_NUMBER = 26;

    static class Node {
        int left, right;
        Node(int left, int right) {
            this.left = left;
            this.right = right;
        }
    }

    public static void main(String[] args) throws IOException {
        Node[] nodes = new Node[MAX_NODE_NUMBER + 1];
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        while (n-- > 0) {
            StringTokenizer st = new StringTokenizer(in.readLine(), " ");
            int x = st.nextToken().charAt(0) - 'A';
            char y = st.nextToken().charAt(0);
            char z = st.nextToken().charAt(0);
            int left = -1;
            int right = -1;
            if (y != '.') left = y - 'A';
            if (z != '.') right = z - 'A';

            nodes[x] = new Node(left, right);
        }

        preorder(nodes, 0);
        System.out.println();

        inorder(nodes, 0);
        System.out.println();

        postorder(nodes, 0);
        System.out.println();

    }

    private static void postorder(Node[] nodes, int x) {
        if (x == -1) return;
        postorder(nodes, nodes[x].left);
        postorder(nodes, nodes[x].right);
        System.out.print((char)(x + 'A'));
    }

    private static void inorder(Node[] nodes, int x) {
        if (x == -1) return;
        inorder(nodes, nodes[x].left);
        System.out.print((char)(x + 'A'));
        inorder(nodes, nodes[x].right);
    }

    private static void preorder(Node[] nodes, int x) {
        if (x == -1) return;
        System.out.print((char)(x + 'A'));
        preorder(nodes, nodes[x].left);
        preorder(nodes, nodes[x].right);
    }
}

https://www.acmicpc.net/problem/10844

문제

45656이란 수를 보자.

이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. 

(0으로 시작하는 수는 없다.).

풀이

 1) 문제를 한글로 풀어본다.

 D(N) = 길이가 N인 계단 수의 개수 

 2) 점화식을 만든다.

 D[N][L] = D[N-1][L-1] + D[N-1][L+1]

• L =    0 :  D[N][L] = D[N - 1][L + 1]

• L = (1 ~ 8) : D[N][L] = D[N - 1][L - 1] + D[N - 1][L + 1]

• L =    9 : D[N][L] = D[N - 1][L - 1]

 3) 코딩

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

/**
 * 쉬운 계단 수
 * https://www.acmicpc.net/problem/10844
 *
 * 문제
 * 45656이란 수를 보자.
 * 이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.
 * 세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.
 * N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)
 *
 * 입력
 * 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.
 *
 * 출력
 * 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
 *
 * 예제 입력 1
 * 1
 * 예제 출력 1
 * 9
 * 예제 입력 2
 * 2
 * 예제 출력 2
 * 17
 */
public class BOJ_10844_쉬운계단수 {
    static final long MOD = 1000000000;

    public static void main(String[] args) throws IOException {

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());

        long[][] d = new long[n+1][10];

        for (int i = 1; i <= 9; i++) {
            d[1][i] = 1;
        }

        for (int i = 2; i <= n; i++) {
            for (int j = 0; j <= 9; j++) {
                d[i][j] = 0;
                if (j - 1 >= 0) d[i][j] += d[i-1][j-1];
                if (j + 1 <= 9) d[i][j] += d[i-1][j+1];
                d[i][j] %= MOD;
            }
        }

        long result = 0;
        for (int i = 0; i <= 9; i++) {
            result += d[n][i];
        }

        result %= MOD;

        System.out.println(result);
    }
}