BEAKJOON / 백준 - JAVA 14585번 사수빈탕

2024.08.21기준 - 실버1

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

이 문제는 수빈이가 좌표평면에서 움직일 때 수빈이가 먹을 수 있는 사탕의 최대 개수를 출력하는 문제입니다.

 

1. 우선 전체 탐색을 하기 위해 필요한 변수들을 생성해줍니다.

static int count = 0;
static int maxx, maxy, m;
static int[][] dp; // 현재 위치에서 먹을 수 있는 사탕의 개수
static int[][] map; // 사탕의 개수를 저장하는 배열
static int[] dx = {0, -1}; // 위쪽, 왼쪽
static int[] dy = {-1, 0};

 

수빈이는 위쪽, 오른쪽으로 갈 수 있기 때문에, 현재 좌표의 기준으로는 아래와 왼쪽이여서 0, -1을 이동하도록 했습니다.

 

2. 좌표평명 전체의 크기를 모르기 때문에 좌표를 먼저 따로 저장을 해줍니다.

int x, y;
maxx = 0;
maxy = 0;
int[][] coordinates = new int[n][2]; // 좌표를 저장하는 배열

for (int i = 0; i < n; i++) {
    st = new StringTokenizer(br.readLine());
    x = Integer.parseInt(st.nextToken());
    y = Integer.parseInt(st.nextToken());

    coordinates[i][0] = y;
    coordinates[i][1] = x;

    // 전체 탐색을 위해 최대 행과 열을 구해주기 위한 변수
    maxx = Math.max(maxx, x);
    maxy = Math.max(maxy, y);
}

 

3. 저장된 최대 행과 열 값을 이용해 좌표평면과 사탕의 개수를 저장하는 평면을 만들어 줍니다.

map = new int[maxy + 1][maxx + 1];
dp = new int[maxy + 1][maxx + 1];

 

4. 만들어진 좌표평면에 저장해둔 좌표를 이용해 현재 위치에 있는 사탕의 개수를 저장합니다.

// 저장된 좌표에 사탕의 개수를 저장.
for (int i = 0; i < n; i++) {
    map[coordinates[i][0]][coordinates[i][1]] = m;
}

 

5. 저장된 사탕의 위치를 통해 현재 위치에서 참조하는 위치에 사탕을 먹은 횟수에 좌표평면 위에 있는 사탕개수 - 좌표까지의 거리를 계산을해 dp에 저장을 해줍니다.

// 위치 별 먹을 수 있는 캔디의 개수를 저장하는 함수.
private static void function() {
    // 참조하는 좌표, 거리
    int nexty, nextx, dis;

    for (int i = 0; i <= maxy; i++) {
        for (int j = 0; j <= maxx; j++) {

            // 위쪽, 왼쪽을 확인하는 반복문
            for (int k = 0; k < 2; k++) {
                nexty = i + dy[k];
                nextx = j + dx[k];
                dis = i + j;

                // 평면좌표 위에 있다면, 전에 먹은 사탕의 개수 + 현재 위치에 있는 사탕의 개수 - 현재 좌표까지 지난 시간을 저장해줍니다.
                if (check(nexty, nextx)) {
                    dp[i][j] = Math.max(dp[i][j], dp[nexty][nextx] + (map[i][j] != 0 ? (map[i][j] - dis < 0 ? 0 : map[i][j] - dis) : 0));
                }
            }

            count = Math.max(count, dp[i][j]);
        }
    }
}

// 좌표평면을 벗어나지 않기 위해 체크해주는 함수.
private static boolean check(int y, int x) {
    return 0 <= x && 0 <= y && x <= maxx && y <= maxy; 
}

 

저장을 함과 동시에 최댓값을 구해 값을 저장시켜줍니다.

 

6. 저장된 값을 출력해줍니다.

 

 

코드

package Main;

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

public class Main {
	
	static int count = 0;
	static int maxx, maxy, m;
	static int[][] dp; // 현재 위치에서 먹을 수 있는 사탕의 개수
	static int[][] map; // 사탕의 개수를 저장하는 배열
	static int[] dx = {0, -1}; // 위쪽, 왼쪽
	static int[] dy = {-1, 0};
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		int x, y;
		maxx = 0;
		maxy = 0;
		int[][] coordinates = new int[n][2]; // 좌표를 저장하는 배열
		
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			x = Integer.parseInt(st.nextToken());
			y = Integer.parseInt(st.nextToken());
			
			coordinates[i][0] = y;
			coordinates[i][1] = x;
			
			// 전체 탐색을 위해 최대 행과 열을 구해주기 위한 변수
			maxx = Math.max(maxx, x);
			maxy = Math.max(maxy, y);
		}
		
		map = new int[maxy + 1][maxx + 1];
		dp = new int[maxy + 1][maxx + 1];
		
		// 저장된 좌표에 사탕의 개수를 저장.
		for (int i = 0; i < n; i++) {
			map[coordinates[i][0]][coordinates[i][1]] = m;
		}
		
		function();
		bw.write(Integer.toString(count));
		bw.flush();
		bw.close();
		br.close();
	}
	
	// 위치 별 먹을 수 있는 캔디의 개수를 저장하는 함수.
	private static void function() {
		// 참조하는 좌표, 거리
		int nexty, nextx, dis;
		
		for (int i = 0; i <= maxy; i++) {
			for (int j = 0; j <= maxx; j++) {
				
				// 위쪽, 왼쪽을 확인하는 반복문
				for (int k = 0; k < 2; k++) {
					nexty = i + dy[k];
					nextx = j + dx[k];
					dis = i + j;
					
					// 평면좌표 위에 있다면, 전에 먹은 사탕의 개수 + 현재 위치에 있는 사탕의 개수 - 현재 좌표까지 지난 시간을 저장해줍니다.
					if (check(nexty, nextx)) {
						dp[i][j] = Math.max(dp[i][j], dp[nexty][nextx] + (map[i][j] != 0 ? (map[i][j] - dis < 0 ? 0 : map[i][j] - dis) : 0));
					}
				}
				
				count = Math.max(count, dp[i][j]);
			}
		}
	}
	
	// 좌표평면을 벗어나지 않기 위해 체크해주는 함수.
	private static boolean check(int y, int x) {
		return 0 <= x && 0 <= y && x <= maxx && y <= maxy; 
	}
}