[Softeer]나무 수확 / [백준] 11048 이동하기

https://softeer.ai/practice/7369

Softeer - 현대자동차그룹 SW인재확보플랫폼

위 문제는 레벨3인데 정답률이 조금 낮아서 긴장하고 문제를 읽었다..

 

그런데 백준에서 풀었던 문제와 매~우 유사해서, 

장애물 없이 바로 풀 수 있었다.

 

백준 어떤 문제랑 비슷했더라.. 찾아봤는데

https://www.acmicpc.net/problem/11048

[11048번 이동하기] 문제와 매우 유사하다.

 

소프티어에서 다른점은,

중간에 한 구역에서만 value*2 한 값을 했을 때의 최대값을 구하는 것이다.

 

백준에서는 d[n][m] 값으로 다이나믹한 값을 정하는 변수를 지정했다면,

소프티어에서는 d[n][m][2] 로 배열값을 하나 더 추가하여,

지나간 자리에 value*2 를 한 값이 있는지(스프링쿨러를 설치하여 수확량이 2배되는 경우) 없는지를 체크하여

최대값을 구해주면 된다.

 

레벨3의 모든 문제가 이렇게 풀어본거에서 나와서 쉽게만 풀린다면 얼마나 좋을까...

 

▶ 백준 11048번 이동하기

import java.io.*;

public class Main {

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] nm = br.readLine().split(" ");
        int n = Integer.parseInt(nm[0]);
        int m = Integer.parseInt(nm[1]);

        int[][] a = new int[n+1][m+1];
        int[][] d = new int[n+1][m+1];
        for(int i=1; i<=n; i++){
            String[] line = br.readLine().split(" ");
            for(int j=1; j<=m; j++){
                a[i][j] = Integer.parseInt(line[j-1]);
                d[i][j] = Math.max(d[i-1][j], d[i][j-1]) + a[i][j];
            }
        }
        bw.write(String.valueOf(d[n][m]));
        bw.close();
    }

}

 

▶ Softeer 7369번 나무 수확

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int[][] a = new int[n+1][n+1];
        int[][][] d = new int[n+1][n+1][2];
        for(int i=1; i<=n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=1; j<=n; j++){
                a[i][j] = Integer.parseInt(st.nextToken());
                d[i][j][0] = Math.max(d[i-1][j][0], d[i][j-1][0]) + a[i][j];
                d[i][j][1] = Math.max(d[i-1][j][0], d[i][j-1][0]) + a[i][j]*2;
                d[i][j][1] = Math.max(Math.max(d[i-1][j][1], d[i][j-1][1]) + a[i][j], d[i][j][1]);
            }
        }

        bw.write(String.valueOf(d[n][n][1]));
        bw.close();
    }

}