[코틀린, 자바] BOJ 15645 - 내려가기 2 (boj kotlin java)

문제 : boj15645

 

ps. 코틀린의 경우 대강 인터넷 검색해서 문법을 익혔으므로 아직 늅늅이 상태여서 많이 어색하게 짰다.

 

  이 문제의 경우 dp로 풀면 쉽게 풀린다. 알아야 하는 정보는 바로 직전 3칸의 합계 뿐이다(시작할때는 당연히 셋 다 0이라고 치면 된다.).

 

N개의 줄을 입력받으면서, 매번 해당 칸으로 올 수 있는 값 중 최대와 최소값을 갱신 후에 현재 줄에서 입력받은 값을 더해주면 된다. dp[a][b]가 a라인까지 입력받았을 때 b번째(0,1,2로 3개) 칸까지의 최대합계라고 해보자. 그렇다면

dp[x][0] = max(dp[x-1][0], dp[x-1][1]) + 입력받은 0번째 값

dp[x][1] = max(dp[x-1][0], dp[x-1][1], dp[x-1][2]) +  입력받은 1번째 값

dp[x][2] = max(dp[x-1][1], dp[x-1][2]) + 입력받은 2번째 값

이 될 것이다. 그렇다면 최종적으로 N개의 줄을 모두 입력받은 후 최대 점수는 max(dp[n][0], dp[n][1], dp[n][2])가 될 것이다. 최소값은 위에서 max대신 min 값을 판단해주면 된다.

 

  이하 코드에서 코틀린으로 짠 코드의 경우엔 어차피 바로 직전의 정보만 알면 되므로 3칸짜리 배열을 사용해 dp를 진행했다. 코틀린은 아직 어색하므로 자바로 새로짜본 거에선 똑같은 로직으로 하면 재미없으니 dp[a][b][c]를 a번째 줄의 b번째 열의 최대(c=0), 최소(c=1)로 정의해 짜봤다.

 

 

 

코드(코틀린) : github

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.StringTokenizer

const val VALUE_SUM_LIMIT = 9*100000+1

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    var n = readLine().toInt()
    var max = Array(3){0}
    var min = Array(3){0}
    while(n-->0) {
        val st = StringTokenizer(readLine())
        val maxTmp = Array(3){0}
        val minTmp = Array(3){VALUE_SUM_LIMIT}
        var i = 0
        while (st.hasMoreTokens()) {
            val cur = st.nextToken().toInt()
            for (j in i-1..i+1) {
                if (j < 0 || j >= 3) continue
                maxTmp[i] = Math.max(maxTmp[i], max[j])
                minTmp[i] = Math.min(minTmp[i], min[j])
            }
            maxTmp[i]+=cur
            minTmp[i]+=cur
            i++
        }
        max = maxTmp
        min = minTmp
    }
    println("${max.toList().maxOrNull()} ${min.toList().minOrNull()}")
}

 

 

코드(자바) : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static final int VALUE_SUM_LIMIT = 9*100000+1;
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][][] dp = new int[n+1][3][2];
        for (int i = 1; i <= n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 3; j++) {
                int cur = Integer.parseInt(st.nextToken());
                dp[i][j][1] = VALUE_SUM_LIMIT;
                for (int k = j-1; k <= j+1; k++) {
                    if (k < 0 || k >= 3) continue;
                    dp[i][j][0] = Math.max(dp[i][j][0], dp[i-1][k][0]);
                    dp[i][j][1] = Math.min(dp[i][j][1], dp[i-1][k][1]);
                }
                dp[i][j][0]+=cur;
                dp[i][j][1]+=cur;
            }
        }
        int max = Math.max(dp[n][0][0], Math.max(dp[n][1][0], dp[n][2][0]));
        int min = Math.min(dp[n][0][1], Math.min(dp[n][1][1], dp[n][2][1]));
        System.out.println(max + " " + min);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}