[백준] 1959번: 달팽이3

https://www.acmicpc.net/problem/1959

1959번: 달팽이3

처음부터 2차원 배열을 만들어서 구현할 생각은 애시당초 접는다. 지나치게 m, n의 범위가 크기 때문이다.

대신에 상하좌우 이동 제한의 변수를 만들어서 반복적으로 탐색을 하려했는데, 이것도 시간초과가 발생한다.

결국엔 공식을 파악해서 조건문으로 문제를 풀어야 한다.

빠르게 공식을 구하기는 어렵고, 스스로 케이스를 나눠서 공식을 추리해야 한다.

 

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    long m, n;
    cin >> m >> n;
    
    if(m > n) {
        // 좌 + 우 + 한 번 더 꺾기 때문
        printf("%ld\n", 2 * (n - 1) + 1);
    }
    else {
        printf("%ld\n", 2 * (m - 1));
    }
    if(m == n) {
        if(m % 2 == 1) {
            printf("%ld %ld", (m - 1) / 2 + 1, (m - 1) / 2 + 1);
        }
        else {
            printf("%ld %ld", m / 2 + 1,  m / 2);
        }
    }
    else {
        if(n > m) {
            if(m % 2 == 0) {
                printf("%ld %ld", m / 2 + 1, m / 2);
            }
            else {
                printf("%ld %ld", m / 2 + 1, m / 2 + 1 + (n - m));
            }
        }
        else {
            if(n % 2 == 0) {
                printf("%ld %ld", n / 2 + 1, n / 2);
            }
            else {
                printf("%ld %ld", n / 2 + 1 + (m - n), n / 2 + 1);
            }
        }
    }
}