[BOJ][1783] 병든 나이트

1. 문제 링크

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

2. 사용 알고리즘

그리디

3. 풀이

1) 높이가 1인 경우

• 이동할 수 있는 곳이 없으므로 현재 위치 1개

2) 높이가 2인 경우

• {1칸 위로, 2칸 오른쪽} 또는 {1칸 아래로, 2칸 오른쪽} 2가지 경우 가능

• 한 번에 두 칸씩 오른쪽으로 가게 되므로 (m + 1) / 2개

• 단, 이동 횟수가 4번보다 많은 경우 이동 방법을 모두 한 번씩은 사용해야됨

• ∴ min(4, (m + 1) / 2)

3) 높이가 3이상인 경우

• 너비가 7이상인 경우

  • 이동 방법을 모두 한 번씩 사용하면 너비가 7필요

  • 8부터는 {2칸 위로, 1칸 오른쪽} 또는 {2칸 아래로, 1칸 오른쪽} 반복

  • ∴ m - 2

• 너비가 7미만인 경우

- {2칸 위로, 1칸 오른쪽} 또는 {2칸 아래로, 1칸 오른쪽} 반복

- 단, 이동 횟수가 4번보다 많은 경우 이동 방법을 모두 한 번씩은 사용해야됨

- ∴ min(4, m)

∴ 위의 조건을 만족하는 경우, 주어진 수를 내림차순 정렬한 값이 답이된다.

4. 소스 코드

4-1. C++

https://github.com/dev-aiden/problem-solving/blob/main/boj/1783.cpp

#include <iostream>
#include <algorithm>

using namespace std;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n, m; cin >> n >> m;
    if(n == 1) {
        cout << 1 << "\n";
    } else if(n == 2) {
        cout << min(4, (m + 1) / 2) << "\n";
    } else if(n >= 3) {
        if(m >= 7) cout << m - 2 << "\n";
        else cout << min(4, m) << "\n";
    }
    return 0;
}

4-2. JAVA

https://github.com/dev-aiden/problem-solving/blob/main/boj/1783.java

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        if(n == 1) {
            System.out.println(1);
        } else if(n == 2) {
            System.out.println(Math.min(4, (m + 1) / 2));
        } else if(n >= 3) {
            if(m >= 7) System.out.println(m - 2);
            else System.out.println(Math.min(4, m));
        }
    }
}