백준 1959 달팽이3 Kotlin (수학)

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

1959번: 달팽이3

문제

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

ㅇ

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

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

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

입력

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

출력

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

알고리즘 분류

• 수학
• 많은 조건 분기

풀이

2021.12.08 - [알고리즘 문제 풀이/백준] - 백준 1952 달팽이2 Kotlin (수학)

골드3 치곤 좀 쉬운 것 같다.

이전 달팽이2를 풀고와서 그런가?

 

2,2부터 6,6 정도까지의 그래프를 직접 그려보는데,

2,3, 2,4, 4,2

3,4, 3,5, 5,3

4,5, 4,6, 6,4

처럼 행과 열도 증가시켜본다.

이런 식으로 2,2~6,6까지 몇 개 그려보면 모든 규칙이 나온다.

이 규칙들을 분기해서 출력만 하면 끝

 

별다른 설명이 필요 없다.

이 규칙을 찾는 것은 어렵지 않으니, 남이 올린 규칙을 보는 것보다 본인이 직접 해 보는 것이 더 좋을 것 같다.

 

코드

import kotlin.math.*
fun main() = with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    br.readLine().split(' ').map{it.toLong()}.also{
        val m =it[0]
        val n = it[1]
        if(m==n){
            write("${2*(n-1)}\n")
            if(m%2==0L){
                write("${(m/2)+1} ${n/2}")
            }
            else{
                write("${(m/2)+1} ${(m/2)+1}")
            }
        }
        else {
            if(m>n){
                write("${2 * (min(n, m) - 1) + 1}\n")
            }
            else{
                write("${2*(m-1)}\n")
            }
            if(min(m,n)%2==0L){
                write("${min(m,n)-(min(m,n)/2-1)} ${min(m,n)-min(m,n)/2}")
            }
            else{
                write("${m-(min(m,n)/2)} ${n-(min(m,n)/2)}")
            }
        }
    }
    close()
}