1783 : 병든 나이트 ( 백준 / java )

www.acmicpc.net/problem/1783

1783번: 병든 나이트

 

 

 

*해결 과정

이 문제는 이동 칸수가 특이합니다. 결론적으로 오른쪽으로만 이동하는 구조입니다.

이 구조를 이용해서 문제를 풀어야합니다. 배열은 최대 각 길이가 20억이 될 수 있기 떄문에 배열을 만들면 터지게 됩니다. 그래서 얼마나 많이 오른쪽으로 잘 이동할 수 있는지 확인합니다. N,M과의 관계를 천천히 살펴봅니다.

 

n=1 : 이동 불가이므로 1을 반환

n=2 : 2,3만 이동 가능하므로 최대 4번 이동 가능

m<7 : 세로 길이가 충분 할 경우, m에 따라서 6이하는 최대 4번 이동 가능

m-2 : 4방향을 다 돌아야 하기 때문에 가로 m길이에서 어쩔 수 없이 2번을 필수로 이동하므로 -2 이후 계속 오른쪽으로 이동

 

import java.util.*; 
public class Main {
 
    static int n,m;
    static Scanner sc = new Scanner(System.in);
    
    public static void main(String[] args) {
        n = sc.nextInt();
        m = sc.nextInt();
        
        System.out.println(solve());
    }
    
    static int solve() {
        if(n == 1) return 1;
        if(n == 2) return Math.min(4, (m+1)/2);
        if(m < 7 ) return Math.min(4, m); 
        return m-2;
    }
}

이렇게 해결문제를 떠올리는 것은 쉽지 않습니다. 특이한 케이스에 대해서 직접 그림을 그리며 접근하면 좀 더 보일 것 같습니다.