1932. 정수 삼각형 (Silver I) [Kotlin]

문제

생각 방식

DP 문제

2차원 배열을 만들어서 입력 값을 다 넣어주기

for loop을 두 번 사용해서 처음엔 row 확인하고 다음으로는 row에 있는 element들 확인해 주기

반복문을 활용해서 각 행의 값을 업데이트해 주기

마지막 줄의 값 중에 max를 찾아서 프린트해 주기

이런 느낌

💻 작성 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().toInt()
	
    # 2차원 배열 만들어주기
    val arr = Array(n) { IntArray(n) }
	
    # 만든 배열에 값 넣어주기
    for (i in 0 until n) {
        val st = StringTokenizer(br.readLine())
        for (j in 0..i) {
            arr[i][j] = st.nextToken().toInt()
        }
    }
	
    # update the array
    for (i in 1 until n) {
        for (j in 0..i) {
            arr[i][j] += when (j) {
                0 -> arr[i - 1][j]
                i -> arr[i - 1][j - 1]
                else -> maxOf(arr[i - 1][j], arr[i - 1][j - 1])
            }
        }
    }

    println(arr.last().maxOrNull())
}

 

⭐️코드 설명

* 2차원 배열 만들어주기 Array(n) { IntArray(n) }

Array(n): n크기의 일차원 배열을 생성한다

{ IntArray(n) }: 행이 n개

그러므로 이 코드로 크기가 n * n인 2차원 배열을 생성한다

 

* 첫 번째 반복문

StringTokenizer는 입력한 문자열을 토큰으로 나눠준다

Java 클래스, 그러므로 Kotlin에서도 사용 가능하다

br.readLine()으로 한 줄을 읽어옴

st는 읽어온 한 줄을 공백을 기준으로 토큰으로 나눠줌

arr:
7  0  0  0  0
3  8  0  0  0
8  1  0  0  0
2  7  4  4  0
4  5  2  6  5

 

* 두 번째 반복문

Case 1: when j = 0

여기서는 j가 0이므로 현재 행의 제일 왼쪽에 위치한다, 이 값을 이전 행의 동일한 열 값을 더해줌

 

Case 2: when j = i

여기서는 j가 i이므로 현재 행의 제일 오른쪽에 위치한다, 이 값을 이전 행의 동일한 열 값을 더해줌 

 

Case 3: when j = 0 < j < i

현재 행의 중간에 위치한다, 이 값을 이전 행의 현재 열과 바로 앞 열 중에서 더 큰 값을 더해준다

# i = 1
arr:
7   0   0   0   0
10  8   0   0   0
8   1   0   0   0
2   7   4   4   0
4   5   2   6   5


# i = 2
arr:
7   0   0   0   0
10  15  0   0   0
18  16  15  0   0
2   7   4   4   0
4   5   2   6   5

 

i =1일 때 두 번째 줄의 8은 변하지 않는 이유

for (j in 0..i) -> 0부터 1까지 돌리니까 0일 때 어떻게 된다고 -> Case1 상황

Case 3

셋째 줄의 1이 i=2일 때 16으로 변하는 것을 볼 수 있다

왜? 10+1 = 11, 15+1=16 이니까 제일 큰 걸 찾아서 저장!  

 

Scanner를 사용할 수 있지만, runtime 문제로 BufferedReader 사용하기

그냥 BufferedReader 사용하자, 대량의 입력을 처리할 때 이게 성능이 더 좋다. 어차피 코딩테스트에서는 무조건 time complexity 줄여야 하니까