Beakjoon 1783 병든 나이트

14 Jan 2021 in Algorithm

문제 링크 : https://www.acmicpc.net/problem/1783

나의 풀이

먼저 병든 나이트의 이동 횟수가 4번보다 적지 않다면 이동 방법을 모두 한 번씩 사용해야 하기 때문에 이동 방법을 모두 한 번씩 사용할 수 있는 조건을 생각해보자
모든 방법을 한 번씩 사용하는 최소한의 체스판 크기는 아래 그림과 같다. (N > 2, M > 6)
이렇게 모든 방법을 한 번씩 사용한 상황에서는 이동 방법에 대한 제약이 없어지고 아래 그림과 같은 패턴을 반복하며 오른쪽으로 이동하는 것만 고려하면 되어 M - 6 + 4로 표현이 가능하다. 여기서 -6은 모든 이동 방법을 한 번씩 사용했을 때 사용되는 가로의 크기이며, 4는 모든 방법을 움직였다는 것을 의미한다.

이제 이동 방법을 모두 사용할 수 없는 경우를 생각해보자
먼저 N == 1 or M == 1일 경우 어떤 방법으로도 움직일 수 없기 때문에 1로 고정한다.
만약 N == 2라면 위, 아래로 1칸 씩 밖에 못 움직이기 때문에 (1칸 위로, 2칸 오른쪽), (1칸 아래로, 2칸 오른쪽) 이 두가지 방법만 사용하여야 한다. 이 때 이 두가지 방법 모두 오른쪽으로 2칸씩 이동하기 때문에 (M-1)/2 + 1 으로 값을 구할 수 있다.
그 외 경우는 세로 방향으로는 제한이 없으나 가로 방향에 제한이 있기 때문에 오른쪽으로 한 칸씩만 이동하는 (2칸 위로, 1칸 오른쪽), (2칸 아래로, 1칸 오른쪽) 두 가지 방법을 사용하기 때문에 M만큼 움직일 수 있다.
단 방문한 칸이 5개 미만일 때만 이동 방법에 제약이 없기 때문에 이동 방법을 모두 사용할 수 없는 경우에 4칸 보다 많이 움직이면 4칸이 최대이기 때문에 4칸으로 처리한다.

풀이 코드 : 1783 병든 나이트

#include <stdio.h>
#include <vector>

using namespace std;

int main(){
    long long N, M;
    scanf("%lld %lld", &N, &M);
    long long answer;
    if(N > 2 && M > 6){
        answer = M - 6 + 4;
    }
    else {
        if(N == 1 || M == 1){
            answer = 1;
        }
        else if(N==2){
            answer = (M-1)/2 + 1;
        }
        else {
            answer = M;
        }

        if(answer > 4){ 
            answer = 4;
        }
    }
    printf("%lld",answer);
}

채점결과