1783번

1783번 - 병든 나이트

이 문제는 어떤 규칙? 어떤 범위를 나눠서 풀 것인가에 대해서는, 푸는 방법을 알았다.

그런데 뭔가 어떤식으로 코드를 일반화를 시켜야 할지, 그게 부족해서 case를 모두 나눠서 풀었다..

N이 3이상이고 M이 7 이상일 때는 답이 M-2 가 나온다는 사실을 알았는데 구현에서 문제가 발생했다.

일단 이 나이트는 무조건 오른쪽으로 움직이게 된다, 따라서 똑같은 자리를 다시 방문할 일이 없기 때문에 생각하기가 쉽다.

처음에는 숫자가 너무 큰데 겹치는 경우가 발생하면 어떡하지 하다가 겹치지 않는다는 사실을 알았다.

그래서 오른쪽으로 2칸 이동하는 2가지 방법을 빼고, 1칸씩 이동하는 것을 썼을 때 최대로 방문횟수가 나오게 된다.

근데 4번 이상에서는 모두 써야 한다는 점에서 다양한 케이스가 나오는데, 이를 일반화하지를 못했다...

############################

다른 사람 코드를 보고 이해해보기.

http://dhpark.kr/425

너무 잘 설명해주셨다.

############################

<정답 코드>

#include<iostream>
 
using namespace std;
 
int main()
{
    int N, M;
    int ans = 0;
    cin >> N >> M;
 
    if (N == 1)
    {
        ans = 1;
    }
    else if (N == 2)
    {
        if (M >= 7)
            ans = 4;
        else if (M >= 5)
            ans = 3;
        else if (M >= 3)
            ans = 2;
        else
            ans = 1;
    }
    else if (N >= 3)
    {
        if (M == 1)
            ans = 1;
        else if (M == 2)
            ans = 2;
        else if (M == 3)
            ans = 3;
        else if (M >= 4 && M <= 6)
            ans = 4;
        else if (M >= 7)
            ans = M - 2;
    }
 
    cout << ans << endl;
 
    return 0;
}

<블로그 보고 내 코드를 다시 옮김>

#include<iostream>
#include<algorithm>
using namespace std;
 
int main()
{
    int N, M;
    int ans = 0;
    cin >> N >> M;
 
    if (N == 1)
    {
        ans = 1;
    }
    else if (N == 2)
    {
        ans = min(3, (M - 1) / 2) + 1;
    }
    else if (N >= 3)
    {
        if (M >= 7)
        {
            ans = M - 2;
        }
        else
        {
            ans = min(3, M - 1) + 1 ;
        }
    }
 
    cout << ans << endl;
 
    return 0;
}