[백준] 달팽이2 (C++)

 

문제 URL:

www.acmicpc.net/problem/1952

1952번: 달팽이2

 

다음 문제는 주어진 M 줄 N칸에서 선이 꺾어지는 횟수를 구하는 프로그램이다.

출력 표의 왼쪽 위 칸(ㅇ)에서 시작하여, 오른쪽으로 선을 그려 나가며

표의 바깥 또는 이미 그려진 칸에 닿아서 더 이상 이동할 수 없게 되면, 시계방향으로 선을 꺾어서 그려나간다.

아래는 M=5, N=3의 예이다.

 

ㅇ	→	↘
↗	↘	↓
↑	↓	↓
↑	끝	↓
↖	←	↙

 

이 문제를 처음 봤을 때는 규칙을 어떻게 찾아야 할지 고민했는데

결국 행과 열의 각 경우에 따라 각각의 예시를 작성하여 규칙을 찾아냈다. 

 

처음에는 홀짝에 따라서 규칙이 생기는 줄 알고 행과 열 순으로 홀/홀 짝/짝 홀/짝 짝/홀 이렇게 진행을 해봤는데

하다 보니 행의 길이와 열의 길이에 따라서 값이 달라지는 것을 깨달았다. 

 

이렇게 찾아낸 규칙을 보면 다음과 같다.

 

만약 MxN행렬 중 M(행)이 더 짧다면, MxN행렬의 꺾어지는 횟수는 MxM행렬의 꺾어지는 횟수와 같고,

N(열)이 더 짧다면, MxN행렬의 꺾어지는 횟수는 (NxN행렬의 꺾어지는 횟수+1)이 된다.

이는 각각의 행렬을 그림으로 그려보면 더 쉽게 알 수 있다. 

 

여기서 정사각형 행렬이 꺾어지는 횟수는 (한 변의 길이-1)*2이므로

M과 N 중 더 짧은 길이를 찾고 이에 따라 식을 작성해주면 주어진 행렬에서 꺾어지는 횟수를 구할 수 있다. 

---

#include<iostream>
using namespace std;

int main()
{
    int m, n, num, result;
    cin >> m >> n;
    
    if(m>n)
    {
        num = n;
        result = (num-1)*2+1;
    }
    else
    {
        num = m;
        result = (num-1)*2;
    }
    
    cout << result;
}