더 이상 물러설 곳이 없다

www.acmicpc.net/problem/11727

문제

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

예제 입력 1

2

예제 출력 1

3

예제 입력 2

8

예제 출력 2

171

예제 입력 3

12

예제 출력 3

2731

풀이 .

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2] * 2) % 10007;
        }
        System.out.println(dp[n]);
    }
}

'2×n 타일링' 문제에서 조금만 수정하여 해결했다.

n-2까지 채운 후 남아있는 4칸을 채우는 방법은 2x2 블록 하나를 놓는 방법과 2x1 가로블럭 두개를 놓는 방법, 총 2개가 존재하기 때문에 dp[n-2] * 2를 해주었다.

www.acmicpc.net/problem/11726

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

예제 입력 1

2

예제 출력 1

2

예제 입력 2

9

예제 출력 2

55

풀이 .

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;
        }
        System.out.println(dp[n]);
    }
}

n번째 칸을 채울 수 있는 경우는 두가지가 있다.

1. n-1번째까지 모두 채운 후 n번째에 세로블럭 하나를 놓는다.

2. n-2번째까지 모두 채운 후 n-1, n번째에 가로블럭 둘을 놓는다.

dp[n] = "n번째까지 타일을 채울 수 있는 모든 경우의 수" 라고 한다면

dp[n] = dp[n-1] + dp[n-2] 로 해결이 가능하다.

접근은 잘 했는데 초기화 문제 때문에 ArrayIndexOutOfBounds 런타임 에러로 애를 먹었다.

dp[0] = 0;

dp[1] = 1;

dp[2] = 2

로 초기화를 하고 i = 3부터 반복을 돌렸는데, 이렇게 하면 n = 1 일 때, dp[2] 에서 배열 범위 문제가 발생한다.

초기화 부분을 수정하여 정답처리 되었다.

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

n-2에서 세로블럭을 두 개 놓아서 채우는 경우를 고려하지 않는 이유?

-> 이건 이미 n-1에서 세로블럭 놓는 경우에 포함되어있음 (연속된 세로블럭을 놓는 것이므로)

www.acmicpc.net/problem/1463

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

예제 입력 1

2

예제 출력 1

1

예제 입력 2

10

예제 출력 2

3

풀이 .

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 0;

        for(int i = 2; i <= n; i++) {
            int temp = n;
            if(i % 3 == 0) temp = Math.min(temp, dp[i / 3]);
            if(i % 2 == 0) temp = Math.min(temp, dp[i / 2]);
            temp = Math.min(temp, dp[i - 1]);
            dp[i] = temp + 1;
        }
        System.out.println(dp[n]);
    }
}

전형적인 DP 문제이다.

문제는 n을 1로 만들 것을 요구하지만 1을 n으로 만드는 식으로 풀어냈다.

(dp[n] = 1에서 n으로 도달하기 위한 최소 연산 회수)

만약 n에 1, 2, 3 모든 연산을 사용할 수 있는 수라면, n으로 올 수 있는 숫자의 경우의 수는 총 셋이다.

1. (n / 3) * 3

2. (n / 2) * 2

3. (n - 1) + 1

다시 말하면 n/3, n/2, n-1에서 한 번의 연산만 더 수행하면 n이 될 수 있는 것.

즉, dp[n / 3], dp[n / 2], dp[n - 1] 중 최솟값 + 1이 dp[n]이 될 것이다.

그럼 dp[n / 3], dp[n / 2], dp[n - 1] 은 또 어떻게 구하나?

n에서 했던 것처럼 각자 자신에게 올 수 있는 연산들에 대한 경우를 모두 따져보면 된다.

탑 다운, 바텀 업 모두 가능하지만 바텀 업 방식으로 구현했다.

www.acmicpc.net/problem/10992

문제

예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.

입력

첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다.

출력

첫째 줄부터 N번째 줄까지 차례대로 별을 출력한다.

예제 입력 1

1

예제 출력 1

*

예제 입력 2

2

예제 출력 2

 *

***

예제 입력 3

3

예제 출력 3

  *

 * *

*****

예제 입력 4

4

예제 출력 4

   *

  * *

 * * *

******

풀이 .

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        int[] starArr = new int[n + 1];
        int[] spaceArr = new int[n + 1];
        int cnt = 3;
        for(int i = 2; i <= n; i++) {
            starArr[i] = cnt;
            spaceArr[i] = cnt - 2;
            cnt += 2;
        }

        // 첫번째 줄
        for(int i = 1; i <= n - 1; i++) sb.append(" ");
        sb.append("*\n");
        // (2 ~ n-1)번째 줄
        for(int i = 2; i <= n - 1; i++) {
            // 먼저 공백 쭉
            for(int j = n - i; j >= 1; j--) sb.append(" ");
            // "* 공백 쭉 *"
            sb.append("*");
            for(int j = 1; j <= spaceArr[i]; j++) sb.append(" ");
            sb.append("*\n");
        }
        // n번째 줄
        for(int i = 1; i <= starArr[n]; i++) sb.append("*");

        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }
}

예시들을 보고 반복문의 역할을 어떻게 나눌 것인지가 중요

세 개의 큰 반복문으로 나누었다.

1. 첫번째 줄을 찍는 반복문

2. 2~n-1번째 줄을 찍는 반복문

3. n번째 줄을 찍는 반복문

n이 1, 2일 때는 별 사이에 연속적인 공백이 들어가는 줄이 없다.

그래서 두 특수케이스 n=1일때 3으로만 처리, n=2일때 1, 3으로만 처리하도록 하고 나머지는 1, 2, 3으로 해결하도록 했다.

2~n-1번째 줄들에서 별 사이에 들어가는 공백의 수는 1부터 시작해 2개씩 늘어나는 규칙을 이용했다.

www.acmicpc.net/problem/10991

문제

예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.

입력

첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다.

출력

첫째 줄부터 N번째 줄까지 차례대로 별을 출력한다.

예제 입력 1

1

예제 출력 1

*

예제 입력 2

2

예제 출력 2

 *

* *

예제 입력 3

3

예제 출력 3

  *

 * *

* * *

예제 입력 4

4

예제 출력 4

   *

  * *

 * * *

* * * *

풀이 .

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n + 1];
        int cnt = 1;
        for(int i = 1; i <= n; i++) {
            arr[i] = cnt;
            cnt += 2;
        }

        for(int i = 1; i <= n; i++) {
            for(int j = n - i; j >= 1; j--) sb.append(" ");
            for(int j = 1; j <= arr[i]; j++) {
                if(j % 2 == 1) sb.append("*");
                else sb.append(" ");
            }
            sb.append("\n");
        }

        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }
}

www.acmicpc.net/problem/2522

문제

예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.

입력

첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다.

출력

첫째 줄부터 2×N-1번째 줄까지 차례대로 별을 출력한다.

예제 입력 1

3

예제 출력 1

  *

 **

***

 **

  *

풀이 .

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        for(int i = 1; i <= n; i++) {
            for(int j = n - i; j >= 1; j--) sb.append(" ");
            for(int j = 1; j <= i; j++) sb.append("*");
            sb.append("\n");
        }
        for(int i = n - 1; i >= 1; i--) {
            for(int j = 1; j <= n - i; j++) sb.append(" ");
            for(int j = i; j >= 1; j--) sb.append("*");
            sb.append("\n");
        }

        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }
}

www.acmicpc.net/problem/2446

문제

예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.

입력

첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다.

출력

첫째 줄부터 2×N-1번째 줄까지 차례대로 별을 출력한다.

예제 입력 1

5

예제 출력 1

*********

 *******

  *****

   ***

    *

   ***

  *****

 *******

*********

풀이 .

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n + 1];
        int cnt = 1;
        for(int i = 1; i <= n; i++) {
            arr[i] = cnt;
            cnt += 2;
        }

        for(int i = n; i >= 1; i--) {
            for(int j = n - i; j >= 1; j--) sb.append(" ");
            for(int k = 0; k < arr[i]; k++) sb.append("*");
            sb.append("\n");
        }
        for(int i = 2; i <= n; i++) {
            for(int j = n - i; j >= 1; j--) sb.append(" ");
            for(int k = 0; k < arr[i]; k++) sb.append("*");
            sb.append("\n");
        }

        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }
}

www.acmicpc.net/problem/2445

문제

예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.

입력

첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다.

출력

첫째 줄부터 2×N-1번째 줄까지 차례대로 별을 출력한다.

예제 입력 1

5

예제 출력 1

*        *

**      **

***    ***

****  ****

**********

****  ****

***    ***

**      **

*        *

풀이 .

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());

        for(int i = 1; i <= n; i++) {
            // "*", " ", "*"
            for(int j = 1; j <= i; j++) sb.append("*");
            for(int j = (n - i) * 2; j >= 1; j--) sb.append(" ");
            for(int j = 1; j <= i; j++) sb.append("*");
            sb.append("\n");
        }
        for(int i = n - 1; i >= 1; i--) {
            // "*", " ", "*"
            for(int j = 1; j <= i; j++) sb.append("*");
            for(int j = 1; j <= (n - i) * 2; j++) sb.append(" ");
            for(int j = 1; j <= i; j++) sb.append("*");
            sb.append("\n");
        }

        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }
}