[백준-Java] 재귀 4번, 브루트 포스 1번

오늘은 대망의 하노이탑 문제를 포스팅하겠다.

11729번) 하노이탑

하노이탑 문제는 자료구조 시간에 잠깐 다뤄본 적이 있었다.
그 당시에 본 재귀 문제중에 가장 어려운 문제였고, 실제로 코드를 이해하기는 커녕 규칙도 이해 못하고 넘어갔었다.
이번엔 내 것으로 만들겠다는 다짐으로 문제를 풀었다.

하노이탑은 위 사진과 같이 1번에 있는 원반들을 3번으로 옮기는 문제이다.
여기서 모두를 곤란하게 하는 규칙이 두가지 있다.

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

바로 덥석 집어 옮기면 금방 해결될 문제이지만 위 규칙 하에 풀려면 꽤 오랜 시간이 걸린다.

여기서 2번 규칙을 주목해보자.
항상 위의 것이 아래의 것보다 작아야 한다면 원판이 3개라면 반드시 그 위의 2개의 모양을 먼저 만들어준 후에 진행해야 한다.

그렇다면 5개인 경우에는 4개인 경우를 먼저 수행해야하고 4개를 수행하려면 3개를 먼저 수행해야한다.
그러므로 1개가 될때 까지 재귀호출하면 그때 출력을 해주는 방법을 사용하겠다.

[ex) hanoi(3, from, to, by)
= hanoi(2, from, by, to) + move(3, from, to) + hanoi(2, by, to, from)
= hanoi(1, from, to, by) + move(2, from, by) + hanoi(1, to, by, from) + move(3, from, to) + ...]

주의할 점은 이번에도 역시 print함수를 사용하지 않는다는 점이다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        sb.append((int)Math.pow(2,T) -1);
        sb.append("\n");
        hanoi(T, 1, 3, 2, sb);
        System.out.print(sb);
    }
    public static void move(int n, int from, int to, StringBuilder sb){
        String result = String.format("%d %d", from, to);
        sb.append(result + "\n");
    }
    public static void hanoi(int t, int from, int to, int by, StringBuilder sb){
        if(t == 1) move(1, from, to, sb);
        else{
            hanoi(t-1, from, by, to, sb);
            move(t, from, to, sb);
            hanoi(t-1, by, to, from, sb);
        }
    }
}

2798번) 블랙잭

오랜만에 보는 정렬과 탐색 알고리즘이다.

3장의 합이 M을 넘으면 안된다는 조건이기 때문에
오름차순으로 정렬 후에 탐색을 진행하였다.

순차 탐색으로 시간초과가 뜨지 않을까 걱정했는데 다행히도 문제는 없었다.
다음에는 다른 탐색 방법으로 문제를 접근해봐야겠다는 생각이 들었다.

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

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

        int N = Integer.parseInt(str_T.split(" ")[0]);
        int M = Integer.parseInt(str_T.split(" ")[1]);
        int max_res = 0;
        int[] card_deck = new int[N];
        for(int i = 0; i < N; i++){
            card_deck[i] = Integer.parseInt(card_num.split(" ")[i]);
        }
        Arrays.sort(card_deck);
        for(int i = 0; i < N-2; i++){
            for(int j = i+1; j < N; j++){
                int max = card_deck[i]+card_deck[j];
                int count = N-1;
                while(count != j){
                    if(M < max+card_deck[count]) count--;
                    else{
                        if(max_res < max+card_deck[count]) max_res = max+card_deck[count];
                        break;
                    }
                }
            }
        }
        System.out.print(max_res);


    }
}