[백준, BOJ 2281] 데스노트 (java)

728x90

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

2281번: 데스노트

첫째 줄에 n(1 ≤ n ≤ 1,000), m(1 ≤ m ≤ 1,000)이 주어진다. m은 노트의 가로 칸의 개수(폭, 너비)이다. 다음 n개의 줄에는 각 사람의 이름의 길이가 노트에 적어야 할 순서대로 주어진다. 각 길이는 m

www.acmicpc.net

728x90

메모리: 19,096 KB , 시간: 188 ms

사용 알고리즘: 다이나믹 프로그래밍
참고

https://velog.io/@bokiri409/BOJ-%EB%8D%B0%EC%8A%A4%EB%85%B8%ED%8A%B8-2281%EB%B2%88

[BOJ] 데스노트 - 2281번

🎃문제설명🧛사악한 라이토는 기발한 방법을 이용하여 L(애칭 섊)을 살해한 뒤 데스노트를 다시 손에 넣었다. 라이토는 이제 이 노트에 n명의 이름을 적어 넣으려고 한다. 이때 다음과 같은 조

velog.io

 import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
 
    static int n; // 이름 수
    static int m; // 노트의 가로 칸의 개수
    static int[] names; // names[i] := i번째 적어야할 이름의 길이
 
    static int[][] dp;
 
    public static void main(String[] args) throws Exception{
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        // n := 적어야 하는 이름 수, m := 노트의 가로 칸의 개수
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
 
        // names[i] := i번째 적어야할 이름의 길이
        names = new int[n];
        for (int i = 0; i < n; i++) {
            names[i] = Integer.parseInt(br.readLine());
        }
 
        dp = new int[n][m + 2];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], -1);
        }
 
        int result = check(1, names[0] + 1);
        System.out.println(result);
    }
 
    static int check(int index, int cnt) { // index := 이름 순서, cnt := 현재 줄에 채워진 칸 + 1
 
        // 마지막은 항상 0
        if(index == n) return 0;
 
        // 이미 확인한 경우라면 넘어감
        if(dp[index][cnt] != -1) return dp[index][cnt];
 
        int ret;
 
        // 1. 새로운 줄에 쓰는 경우
        ret = check(index + 1, names[index] + 1) + (int)Math.pow(m - cnt + 1, 2);
 
        // 2. 현재 줄에 쓰는 경우
        if(m >= cnt + names[index]) {
            ret = Math.min(ret, check(index + 1, cnt + names[index] + 1));
        }
 
        dp[index][cnt] = ret;
        return ret;
    }
}

728x90

'Problem Solving > BOJ' 카테고리의 다른 글

[백준, BOJ 1477] 휴게소 세우기 (java) (1)	2023.11.27
[백준, BOJ 1548] 부분 삼각 수열 (java) (0)	2023.11.23
[백준, BOJ 19942] 다이어트 (java) (1)	2023.11.21
[백준, BOJ 1720] 타일 코드 (java) (1)	2023.11.14
[백준, BOJ 27653] 최소 트리 분할 (java) (1)	2023.11.09

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

[백준, BOJ 2281] 데스노트 (java)

'Problem Solving > BOJ' 카테고리의 다른 글

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역

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

	public class Main {

	static int n; // 이름 수
	static int m; // 노트의 가로 칸의 개수
	static int[] names; // names[i] := i번째 적어야할 이름의 길이

	static int[][] dp;

	public static void main(String[] args) throws Exception{

	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

	// n := 적어야 하는 이름 수, m := 노트의 가로 칸의 개수
	StringTokenizer st = new StringTokenizer(br.readLine());
	n = Integer.parseInt(st.nextToken());
	m = Integer.parseInt(st.nextToken());

	// names[i] := i번째 적어야할 이름의 길이
	names = new int[n];
	for (int i = 0; i < n; i++) {
	names[i] = Integer.parseInt(br.readLine());
	}

	dp = new int[n][m + 2];
	for (int i = 0; i < n; i++) {
	Arrays.fill(dp[i], -1);
	}

	int result = check(1, names[0] + 1);
	System.out.println(result);
	}

	static int check(int index, int cnt) { // index := 이름 순서, cnt := 현재 줄에 채워진 칸 + 1

	// 마지막은 항상 0
	if(index == n) return 0;

	// 이미 확인한 경우라면 넘어감
	if(dp[index][cnt] != -1) return dp[index][cnt];

	int ret;

	// 1. 새로운 줄에 쓰는 경우
	ret = check(index + 1, names[index] + 1) + (int)Math.pow(m - cnt + 1, 2);

	// 2. 현재 줄에 쓰는 경우
	if(m >= cnt + names[index]) {
	ret = Math.min(ret, check(index + 1, cnt + names[index] + 1));
	}

	dp[index][cnt] = ret;
	return ret;
	}
	}