백준 #1783 / 병든 나이트
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 1260 | 523 | 466 | 41.533% |
문제
병든 나이트가 N * M 크기 체스판의 가장 왼쪽아래 칸에 위치해 있다. 병든 나이트는 건강한 보통 체스의 나이트와 다르게 4가지로만 움직일 수 있다.
- 2칸 위로, 1칸 오른쪽
- 1칸 위로, 2칸 오른쪽
- 1칸 아래로, 2칸 오른쪽
- 2칸 아래로, 1칸 오른쪽
병든 나이트는 병들었지만, 그래도 명색이 체스 나이트이기 때문에 많은 칸을 방문하고 싶어 한다. 병든 나이트의 이동에는 제약이 있다. 만약, 이동 횟수가 4번 초과인 경우에는 위의 이동 방법을 각각 한 번씩 이용해야 한다.
체스판의 크기가 주어졌을 때, 병든 나이트가 방문할 수 있는 칸의 최대 개수를 출력하는 프로그램을 작성하시오. 처음에 있는 칸도 센다.
입력
첫째 줄에 체스판의 세로 길이 N과, 둘째 줄에 체스판의 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다.
출력
병든 나이트가 방문할 수 있는 칸의 개수중 최대값을 출력한다.
// 주석
- 문제 설명 매우매우매우매우매우 부족함
- 아무리 봐도 무슨 말인지 이해가 안돼서 다른 블로그들 참고해봤으나, 뭔소린지 이해가 안됨.
- 그래서 내 나름대로 조건을 설정하고, 그 조건대로 풀어보니까 풀림. 다른 블로그 다 들려봐도 뭔소린지 이해가 안된다면 잘 오셨습니다.
[How To Solve?]
- 조건에서, 이 부분이 추가가 되어야 합니다.
- 1번 조건 : 2칸 위로, 1칸 오른쪽
- 2번 조건 : 1칸 위로, 2칸 오른쪽
- 3번 조건 : 1칸 아래로, 2칸 오른쪽
- 4번 조건 : 2칸 아래로, 1칸 오른쪽
- "병든 나이트가 4회 이동 후, 다섯번 째 움직임 부터는 1번 조건부터 4번 조건까지 모두 무.조.건 한 번씩 이동해야 합니다"
- 위의 말은 즉, 4회 이동 후, 위의 네 조건 중 하나라도 만족시킬 수 없다면 이동이 불가능하다는 점입니다.
- 즉 4회 이동 후, 조건 중 하나라도 만족시키지 못할 것 같다 싶으면 아예 이동을 시도조차 할 수 없다는 의미가 됩니다.
- 위의 조건만 추가 된다면, 굉장히 쉬운 문제가 되어 버립니다.
[Code 분석]
1 | if (N == 1); // 1이면 이동 불가능. | cs |
- N이 1이라면 위, 아래 아무데도 갈 수 없기 때문에 현재 칸에서 움직일 수 없습니다.
- 그래서 움직인 칸은 현재 위치해 있는 칸으로 1이 됩니다.
1 2 3 4 5 | else if (N == 2) { total_cnt = (M - 1) / 2; total_cnt = total_cnt > 3 ? 3 : total_cnt; } | cs |
- N이 2라면, 오오위(오른쪽 오른쪽 위)로 갔다가 오오아(오른쪽 오른쪽 아래)로 갔다가를 반복하면서 오른쪽으로 두 칸씩 이동합니다.
- 여기에서 앞서 말했던 조건이 들어가게 된다면, 최대로 이동할 수 있는 횟수는 4번입니다.
- 왜냐면, 위로 2칸 혹은 아래로 2칸 가는 조건은 사용할 수 없어서 무조건 4번이 MAX가 되기 때문입니다.
(조건 중 하나라도 충족시킬 수 없으면 이동을 시도조차 할 수 없다고 했습니다)
- 하지만 위에서 3으로 표현한 이유는, 시작 위치에 있는 칸을 마지막에 printf로 답 출력시 추가해줄 것이기 때문입니다.
- M-1은 뭐지? 싶으실텐데, 만약 가로 길이가 7이라면, 1 2 3 4 5 6 7 이 가로 인덱스가 될 것입니다.
- 시작점이 1의 왼쪽인 0이라면 M이 되겠지만, 1에서 시작하므로 이동할 수 있는 칸들은 1을 제외한 나머지. 그래서 -1이 필요한 것!
- 대소비교를 해주는 이유는, 세로 길이만 제한 해줬기 때문에 가로 길이가 더 짧아지면 최대 이동 횟수보다 작을 수 있기 때문입니다.
1 2 3 4 | else if (M < 7) { total_cnt = M - 1; total_cnt = total_cnt > 3 ? 3 : total_cnt; } | cs |
- 세로길이만 제한해주면 안되겠죠. 가로 길이가 제한되었을 때도 봐주어야 합니다.
- 가로 길이가 6이라고 가정해봅시다. 세로는 뭐가 됐든 상관이 없습니다.
- 왜냐면 가로로는 무조건 오른쪽으로만 가지만 세로는 위로 갔다가 아래로도 갈 수 있기 때문이죠
- 병든 나이트가 최대한 많은 위치를 방문해보기 위해서는, 오른쪽으로 1칸씩 가는 방법을 택해줘야 합니다.
- 왜냐구요? 세로는 상관이 없으니까 가로로 최대한 촘촘히 가야죠. 가장 많이 방문하고 싶은데 2칸씩 이동하는 바보는 없겠죠
- 그래서 시작점 1을 뺀 나머지를 1칸씩 방문하면 모두 방문할 수 있기 때문에 total_cnt 는 M-1이 됩니다.
- 여기서도 조건을 생각해주어야 합니다. 1칸씩 촘촘히가면 참 좋겠지만, 이동 횟수가 4회를 초과하면 조건을 모두 만족시켜야 하기 때문이죠
- 그렇게 되면 가로 길이를 넘어가기 때문에, 이동 횟수 4회 내에서 가장 촘촘히 이동할 수 있는 방법을 찾아줘야 합니다.
1 2 | else total_cnt = 4 + M - 7; | cs |
- 위에서 모든 예외처리를 해줬기 때문에 나머지 경우들은 편하게 움직이면 됩니다.
- 일단 네 번은 움직일 수 있습니다. 이동 횟수가 4회를 초과하여도 조건을 다 만족시키면서 움직일 수 있는 가로와 세로 길이를 갖고 있기 때문.
- 1번 조건부터 4번 조건까지 모두 사용하면서 이동했다면, 세로로는 시작 위치가 되면서 가로로는 6칸을 가게 됩니다.
- 즉, 처음 위치로부터 6칸 더 갔기 때문에 가로 길이인 M 에서 7을 빼주게 됩니다.
- 정리하자면 4회 이동을 하면 4칸을 방문할 수 있고(+4) 8번째 칸 부터 자유롭게 움직일 수 있기 때문에 움직일 수 있는 나머지 길이는
- M - 7이 됩니다.
[Full - Code]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | /* 1. 나이트는 N * M 체스판의 가장 왼쪽 아래 칸에 위치 2. 2상1우, 1상2우, 1하2우, 2하1우로만 움직일 수 있음 3. 최대한 많은 칸을 방문하고 싶어한다. 4. 만약 이동 횟수가 4회 초과라면, 위의 이동 방법을 한 번씩 이용해야 한다. 5. 나이트가 방문할 수 있는 최대 칸의 갯수. 처음의 칸도 센다. 나이트는 (N-1,0)에 위치하고 있다. 여기서부터 상하좌우로 4번까지는 자유롭게 이동. 4번의 횟수가 채워지면, 위의 2번의 방향을 모두 가야함. 갈 수 없는 경우는 return. */ #define _CRT_SECURE_NO_WARNINGS #include<cstdio> int N, M; // N행 M열 int total_cnt; int main() { scanf("%d %d", &N, &M); if (N == 1); else if (N == 2) { total_cnt = (M - 1) / 2; total_cnt = total_cnt > 3 ? 3 : total_cnt; } else if (M < 7) { total_cnt = M - 1; total_cnt = total_cnt > 3 ? 3 : total_cnt; } else total_cnt = 4 + M - 7; printf("%d\n", total_cnt+1); return 0; } | cs |
// 주석 2
- N과 M크기가 20억이 넘기 때문에 배열로 할 생각하면 절대 안됨. 메모리 초과임.