2024. 5. 28. 17:32ㆍIT/BaekJoon
문제 링크
https://www.acmicpc.net/problem/1952
문제
M줄 N칸으로 되어 있는 표 위에, 달팽이 모양으로 선을 그리려고 한다.
위의 그림은 M=5, N=3의 예이다. 이제 표의 왼쪽 위 칸(ㅇ)에서 시작하여, 오른쪽으로 선을 그려 나간다. 표의 바깥 또는 이미 그려진 칸에 닿아서 더 이상 이동할 수 없게 되면, 시계방향으로 선을 꺾어서 그려나간다.
위의 표는 선을 그려 나간 모양을 나타낸 것이다. 선이 꺾어진 부분은 대각선으로 나타내었다. 표의 모든 칸이 채워질 때까지, 선을 몇 번 꺾게 될까?
입력
첫째 줄에 M과 N이 빈 칸을 사이에 두고 주어진다. (2 ≤ M, N ≤ 100)
출력
첫째 줄에 표의 모든 칸이 채워질 때까지 선이 꺾어지는 횟수를 출력한다.
통과한 답안
namespace _1952
{
internal class Program
{
static void Main(string[] args)
{
string[] inputs = Console.ReadLine().Split(' ');
int M = int.Parse(inputs[0]);
int N = int.Parse(inputs[1]);
int cnt = 2 * (Math.Min(M, N) - 1);
if (M > N)
{
cnt++;
}
Console.WriteLine(cnt);
}
}
}
달팽이가 왼쪽 위에서 시작하여 오른쪽으로 출발하고
벽을 만날 때마다 시계방향으로 90도 회전하는 방식으로 진행할 때
주어진 표를 모두 탐험하는데 필요한 회전 횟수를 구하는 문제이다.
분할 정복의 관점에서 접근하면
회전을 하는 경우에 앞으로 나아갈 M 혹은 N이 줄어드는 효과를 가진다는 것을 알 수 있다.
예시로 주어진 5 3의 입력값을 예시로 보면
처음에에 가야할 공간은 5 3이지만
1번 회전한 경우 (1, 1), (1, 2), (1, 3)은 틍과한 상태이기 때문에
남은 공간은 4 3이 남게된다.
(5, 3)에서 회전하는 경우 위에 더해서 (2, 3), (3, 3), (4, 3), (5, 3)은 통과한 상태이기 때문에
남은 공간은 4 2가 남게된다.
이를 계속 진행해보면
(5, 1)에서 회전하는 경우 위에 더해서 (5, 2), (5, 1)은 통과한 상태이기 때문에
남은 공간은 3 2가 남게된다.
(2, 1)에서 회전하는 경우 위에 더해서 (4, 1), (3, 1), (2, 1)은 통과한 상태이기 때문에
남은 공간은 3 1이 남게된다.
(2, 2)에서 회전하는 경우 위에 더해서 (2, 2)는 통과한 상태이기 때문에
남은 공간은 2 1이 남게 된다.
이후에 두 칸을 더 전진하면 모든 공간을 통과하게 된다.
이를 분석하면 처음에 주어진 M과 N 값에서 1회 회전할 때마다
홀수번째 회전에서는 M을 짝수번째 회전에서는 N을 1씩 뺀 공간이 남게 된다.
(1회 탐험을 하는 경우마다 홀수 : N, 짝수 : M 만큼 탐험하므로)
따라서 M과 N을 1씩 줄이다가 0이 되는 순간 모든 공간을 탐험할 수 있게 된다.
이러한 논리로 위와 같은 코드를 작성하게 되었다.
단, M을 먼저 줄이므로 둘 중 M이 먼저 0이 된다면 상관없지만,
N이 먼저 0이 된다면 1회 더 회전해야 모든 공간을 통과할 수 있다.
'IT > BaekJoon' 카테고리의 다른 글
[BAEKJOON] 백준 5365: Decoder (C#) (0) | 2024.05.28 |
---|---|
[BAEKJOON] 백준 2204: 도비의 난독증 테스트 (C#) (0) | 2024.05.28 |
[BAEKJOON] 백준 2530: 인공지능 시계 (C#) (0) | 2024.05.27 |
[BAEKJOON] 백준 1059: 좋은 구간 (C#) (0) | 2024.05.26 |
[BAEKJOON] 백준 1057: 토너먼트 (C#) (0) | 2024.05.26 |