[BOJ][실5][1783] 병든 나이트

문제 링크

문제링크

첫 번째 풀이 : 그리디

알고리즘

• 4번 이상 움직이기 위해서는 이동방법 1,2,3,4를 모두 사용해야 합니다.
• 4번 미만 움직일 때는 이동방법이 상관 없습니다.

문제에서 구해야하는 것은 한 번의 여행에서 방문할 수 있는 칸의 최대 갯수입니다.

이동 방식에 대해서는 아래와 같이 나타낼 수 있습니다.

int dx[4] = { -2,-1,1,2 };
int dy[4] = { 1,2,2,1 };

생각을 해보면, 시작 위치에서 가로는 1칸 또는 2칸이 움직입니다. 세로는 -2칸 ~ +2칸이 움직입니다. 그래서 세로를 기준으로 케이스는 나누어서 생각하는 것이 좋습니다. 가로는 최대 2칸, 세로는 최대 4칸 차이나는데, 입력받은 가로가 세로보다 두 배가 크더라도 가능하도록 case를 나누어야 합니다.

Case work라고 하여 Case를 나누어서 생각해보아야하는 문제 중에서, 가장 가장 많이 푼 문제가 이 문제입니다.

• 높이 = 1 : 시작점에서 움직일 수 없으므로 정답은 1개
• 높이 = 2 : 이동방식 2번과 3번을 번갈아서 사용하면 이동할 수 있습니다. 대신 4번 이상 움직이기 위해서는 이동방식을 모두 사용해야하기 때문에 최대 3번까지만 움직일 수 있습니다. 2번,3번만을 사용하면 홀수에만 도달할 수 있고, 최대 3번까지의 여행만 할 수 있으므로 정답은 min(4, (m+1)/2)

1	2	3	4	5	6	7	8	9
		x				x
x				x				x(불가능)

• 높이 >= 3 : 높이를 최대한 덜 변화시키면서 이동방식을 모두 사용하는 방법은 아래와 같습니다. 즉, 높이가 3이상이라면 가로의 길이를 모두 활용할 수 있는 최소 조건이 만족된 것입니다. 아래의 표를 보면 n은 변하지 않고 m만 6칸 움직이고 모든 이동방식을 사용했습니다. 이제부터는 유리한 이동방법을 고르고 계속 사용해도 됩니다. 1번+4번을 반복하면 7이상의 모든 m번째 행을 방문할 수 있습니다. 따라서 정답은 아래와 같습니다.

1	2	3	4	5	6	7
	x
				x
x		x				x

if(n>=3){
    if(m <=3) ans = m;
    else if(m <=6) ans = 4;
    else ans = m - 2;
}

또는

if(n>=3){
    if(m <=6) ans = min(4,m);
    else ans = m - 2;
}

정답코드

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;

const int MAX = 2'000'000'000;

int n, m, k;

int main()
{
    //freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    int ans = 0;
    if (n == 1) ans = 1;
    else if (n == 2) ans = min(4, (m + 1) / 2);
    else {
        if (m <= 6) ans = min(4, m);
        else ans = m - 2;
    }
    cout << ans;
    return 0;
}

Success Notice: 수고하셨습니다.