[JAVA] 달팽이3_1959

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

1959번: 달팽이3

 

달팽이3 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

1359

312

238

27.902%

문제

M줄 N칸으로 되어 있는 표 위에, 달팽이 모양으로 선을 그리려고 한다.

ㅇ

위의 그림은 M=5, N=3의 예이다. 이제 표의 왼쪽 위 칸(○)에서 시작하여, 오른쪽으로 선을 그려 나간다. 표의 바깥 또는 이미 그려진 칸에 닿아서 더 이상 이동할 수 없게 되면, 시계방향으로 선을 꺾어서 그려나간다.

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

위의 표는 선을 그려 나간 모양을 나타낸 것이다. 선이 꺾어진 부분은 대각선으로 나타내었다.  표의 모든 칸이 채워질 때까지 선을 몇 번 꺾게 될까? 또, 어디에서 끝나게 될까?

입력

첫째 줄에 M과 N이 빈 칸을 사이에 두고 주어진다. (2 ≤ M, N ≤ 2,100,000,000)

출력

첫째 줄에 표의 모든 칸이 채워질 때까지 선이 꺾어지는 횟수를 출력한다. 둘째 줄에 끝나는 점의 좌표를 출력한다. 왼쪽 위 칸의 좌표를 (1, 1), 오른쪽 아래 칸의 좌표를 (M, N)이라고 하자.

예제 입력 1 복사

5 3

예제 출력 1 복사

5
4 2

알고리즘 분류

• 수학
• 많은 조건 분기

 

---

import java.util.Scanner;

public class Main
{
    private static Scanner s = new Scanner(System.in);
    
	public static void main(String[] args) {
	    // 꺾이는 횟수 구하기에서 *2가 되므로 LONG으로 선언해야 함... INT로 선언했다가 오래 헤맴
	    long M = s.nextInt(); // 세로
	    long N = s.nextInt(); // 가로
	    
	    // 이건 알고리즘이 아니라 공식을 찾아내면 됨.
	    
	    
	    
	    // 1. 꺾이는 수 찾기
	    /*
	        크게 M<=N이거나, M>N일 때로 나뉨.
	    */
	    long line = 0;
	    
	    // 1-1. M <= N
	    // (2, X) > 2 || (3, X) > 4 || (4, X) > 6
	    if (M <= N) line = 2*M - 2;
        
        // 1-2. M > N
        // (X, 2) > 3 || (X, 3) > 5 || (X, 4) > 7 ...
	    else line = 2*N - 1;
	    
	    
	    
	    // 2. 마지막 위치 찾기
	    /*
	        크게 M=N 일 때, M>N 일때, N<M일때로 나뉘고,
	        각 경우는 M(혹은 N) 이 짝수일 떄로 분기됨.
	    */
	    
	    long m = Long.MIN_VALUE;
	    long n = Long.MIN_VALUE;
	    
	    // 2-1. M=N
	    if(M == N) {
	        // 2-1-1. M이 짝수
	        if(M%2 == 0) {
	            // 2*2 > (2,1) || 4*4 > (3,2) || (6*6) > (4,3) ...
	            m = (M/2) + 1;
	            n = N/2;
	        }
	        // 2-1-2. M이 홀수
	        else {
	            // 3*3 > (2,2) || 5*5 > (3,3) ...
	            m = (M/2) + 1;
	            n = m;
	        }
	    }
	    
	    // 2-2. M>N
	    else if(M > N) {
	        // 2-2-1. N이 짝수
	        if(N%2 == 0) {
	            // 4*2 > (2,1) || 5*2 > (2,1) || 6*2 > (2,1)
	            // 5*4 > (3,2) || 6*4 > (3,2)
	            m = (N/2) + 1;
	            n = N/2;
	        }
	        // 2-2-2. N이 홀수
	        else {
	            // 4*3 > (3,2) || 5*3 > (4,2) || 6*3 > (5,2)
	            // 6*5 > (4,3) || 7*5 > (5,3)
	            m = M - (N/2);
	            n = N/2 + 1;
	        }
	    }
	    
	    // 2-3. N>M
	    else {
	        // M>N인 상황을 단순하게 M과 N의 값을 뒤집어서 바꿔주면 됨.
	        // 2-3-1. M이 짝수
	        if(M%2 == 0) {
	            m = (M/2) + 1;
	            n = (M/2);
	        }
	        // 2-3-2. M이 홀수
	        else {
	            m = (M/2) + 1;
	            n = N - (M/2);
	        }
	    }
	    
	    System.out.println(line + "\n" + m + " " + n);
    }
}