[Kotlin, S5] 백준 30923번 크냑과 3D 프린터

출처: unsplash.com

 

크냑과 3D 프린터(30923번)

Silver 5

#수학 #기하학

 

문제 내용

 

 

문제 접근

너비와 폭(가로와 세로)이 1이고 높이가 h인 겹쳐 있는 입체 도형의 겉넓이를 구하는 문제이다.

너비와 폭의 넓이가 1 고정이기 때문에 그냥 전체 겉넓이에 겹치는 부분을 빼는 방법을 쓸 수도 있고, 도형의 각 넓이를 일일이 구해주는 방법이 있다.

나는 도형의 각 넓이를 일일이 구해 더해주는 방법을 사용했다.

문제의 예제 1의 도형 구조를 보면,

사진 1-1

입력받은 순서대로 입체 도형이 주어진다.

입체 도형의 너비와 폭이 1이라서 옆면의 넓이는 각 도형의 높이와 같다.

겉넓이를 구하기 위해서는 사각형들의 넓이의 합을 모두 구해주면 된다.

 

사진 1-1의 겉넓이를 구하기 위해서는(정면을 앞이라고 칭하겠다)

<계산식 1>

도형의 앞면과 뒷면의 넓이: hList.sum() * 2

 

<계산식 2>

도형의 윗면과 아랫면의 넓이: N * 2

 

<계산식 3>

도형의 오른쪽면과 왼쪽면의 넓이: hList.first() + hList.last()

 

위 3가지를 구하고 나면 도형 사이의 넓이만 남는데,

<계산식 4>

이 넓이는 겹쳐 있는 도형들의 높이의 차에 절댓값만큼 더해 준다: abs(hList[i] - hList[i+1])

1, 2, 3, 4를 모두 더해 주면 정답이 나온다.

 

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.abs

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val cnt = readLine().toInt()
    val height = readLine().split(" ").map { it.toLong() }
    var surfaceArea: Long = height.sum() * 2 + cnt * 2 + height.first() + height.last()

    for (i in 0 until cnt - 1) {
        surfaceArea += abs(height[i] - height[i + 1])
    }

    println(surfaceArea)
}

 

문제 풀이

도형의 개수와 도형의 높이를 입력받는다.

도형의 겉넓이에 위의 계산식 1, 2, 3을 더해 준다.

도형의 개수 - 1만큼 겹쳐 있는 도형 간의 넓이도 더해 준다.

 

 

문제 해결 과정

구현은 쉬웠다.

너비와 폭을 고려하지 않아도 돼서 체감 난이도가 더 낮았다.

제한이 도형의 개수가 32768이고, 높이 제한도 32768이다. 그래서 도형의 개수가 32768개이고, 모든 도형의 넓이가 32768인 경우에는 int의 범위를 초과해서 오답이 나올 것이다.

1번 공식인 32,768 * 32,768 * 2 = 2,147,483,648이 int 범위의 한도이다.

이 값에 2, 3, 4번 공식을 적용하면 int 범위가 넘어가게 된다.

그럼 78%에서 오답이 나올 것이다.