1783: 병든 나이트

• toc {:toc}

문제 확인하기

풀이

경우의 수를 나누어 문제를 파악해보려 했다. 칸의 시작을 0,0부터 시작으로 설정했다. 나이트가 오른쪽으로만 움직일 수 있다는 점이 핵심이므로 이에 유의해 조건을 설정한다.

• N >= 3
  • 입력받은 경우 높이는 큰 영향을 끼치지 않는다.
  • M >= 7 일 때 이동 방식을 전부 사용할 수 있고, 이동 방식을 전부 사용하면 오른쪽으로 6칸 이동하기 때문에 제외(M-6)한다. 나머지 칸의 경우 2, 3번으로 이동할 수 있기 때문에 1 칸씩 이동 가능해 전부 더해주면 된다.
  • M ⇐ 6 인 경우에는 이동 방식을 전부 사용할 수 없기 때문에 최대 4번 움직일 수 있고, 칸이 증가할수록 1칸씩 더 증가시킬 수 있으므로 적용시켜준다.
• N == 2
  • 1, 4번의 이동 방식은 사용할 수 없다. 때문에 오른쪽으로 두 칸씩 이동해야 한다.
• N == 1
  • 이동할 수 없다.

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
 
LL N, M;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    LL res = 1;
 
    cin >> N >> M;
    N--; M--;
 
    if(N >= 2){
        if(3<=M && M<6) res += 3;
        else if(M==2) res += 2;
        else if(M==1) res += 1;
        else if(M==6) res += 4;
        else if(M==0) res += 0;
        else {
            res += 4;
            res += M-6;
        }
    }
    else if(N == 1){
        if(M >= 6) res += 3;
        else if(M == 5 || M == 4) res += 2;
        else if(M == 2 || M == 3) res += 1;
        else if(M == 0) res += 0;
    }
    else if(N == 0 || M == 0) res += 0;
    else{
        res += 4;
        res += M-6;
    }
 
    cout << res << '\n';
 
    return 0;
}

사실 풀 때는 위처럼 풀이를 하니 상당히 복잡하게 얽힌 것 같았는데 실상 압축해보면 다음과 같다.

• N == 1
  • 이동할 수 없다.
• N == 2
  • 2, 3번만 사용할 수 있기 때문에 오른쪽으로 두 칸씩만 이동할 수 있다.
  • 최대 4번 움직일 수 있다.
  • M ⇐ 6 인 경우 4번보다 적게 움직인다.
  • 두 칸씩 움직일 수 있기 때문에 (M+1)/2로 나타낼 수 있다.
  • min(4, (M+1)/2)
• N은 크지만 M ⇐ 6 인 경우
  • 이동 방식 전부를 사용할 수 없다.
  • 최대 4번 움직일 수 있다.
  • 위로 두 칸 이상 움직일 수 있기 때문에 오른쪽으로 최대로 이동하려면 1 칸씩 움직여야 최대이다.
  • min(4, M) 으로 표현할 수 있다.
• 위 조건에 해당하지 않는 경우
  • 전체 이동 방식을 전부 사용하고 나머지는 오른쪽으로 한 칸씩 이동해 최대로 이동 횟수를 채운다.
  • m-2로 표현할 수 있다.

#include <bits/stdc++.h>
using namespace std;
int main () { 
	ios_base::sync_with_stdio(false); 
	cin.tie(nullptr);  
	int N, M; 
	cin >> n >> m; 
	
	if (n == 1) cout << 1; 
	else if (n == 2) cout << min(4, (m + 1) / 2); 
	else if (m < 7) cout << min(4, m); 
	else cout << m - 2; 
 
	return 0;
}