[BAEKJOON] 백준 1952: 달팽이2 (C#)

문제 링크

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회 더 회전해야 모든 공간을 통과할 수 있다.