문제 링크
문제
티어: 골드 3
알고리즘: dp
입력
첫째 줄에 n(1 ≤ n ≤ 1,000), m(1 ≤ m ≤ 1,000)이 주어진다. m은 노트의 가로 칸의 개수(폭, 너비)이다. 다음 n개의 줄에는 각 사람의 이름의 길이가 노트에 적어야 할 순서대로 주어진다. 각 길이는 m을 넘지 않는 자연수이다.
출력
첫째 줄에 남게 되는 칸 수의 제곱의 합의 최솟값을 출력한다.
풀이
남게 되는 칸수의 제곱의 합의 최솟값을 구해야 한다.
나는 문제를 풀기 위해서 바텀 업으로 진행했다.
먼저, 첫 번째 이름을 써보자
첫 번째 줄에 들어가고, 남은 칸은 M - name[1]이 된다.
두 번째 이름을 쓸 때는 두 가지 케이스로 나눠진다.
- 해당 줄에 이어서 쓰는 경우
- 다음 줄에 쓰는 경우
그래서 두 가지 경우가 된다.
세 번째 이름을 쓸 때도 각 경우가 두 가지 경우로 나눠지기 때문에
총 4가지 경우가 된다.
이렇게 N번 째 이름까지 모든 경우를 구한다면 당연히 시간 초과가 날 것이다.
그래서 dp를 이용해서 중복 처리를 해야 한다.
다시 세 번째 이름을 쓰는 경우로 돌아와서 일단 모든 경우를 써보자
그러면 다음 줄에 쓰는 경우가 각 경우마다 하나 씩 생기는 것을 볼 수 있는데, 같은 이름이 새로운 줄에 쓰이는 여러 case는 하나의 case로 처리할 수 있다.
왜냐하면 다음 이름을 쓸 때도 1, 2 case를 적용할 것이고, 완전히 같아지기 때문이다.
물론 같은 이름이 새로운 줄에 쓰이는 경우부터를 말하는 것이고, 그 전에는 다른 경우이기 때문에 이 중 가장 작은 값을 가져가는 것으로 중복 case를 줄여줄 수 있는 것이다.
그래서 각 이름마다 최대 경우의 수는 3개를 넘지 못한다.
그러면 dp를 세워보자,
dp[A][B] -> A는 현재 작성하고자 하는 이름의 index이고, B는 현재 줄에서 어디 칸까지 사용했는지를 뜻한다.
A와 B가 같다면 dp에 Math.min을 통해 최적값을 저장하기 때문에 case가 늘어나는 것을 방지할 수 있다.
이 풀이의 시간 복잡도는 O(N)이다.
소스 코드
import java.io.*;
import java.util.*;
public class Main {
static int N,M;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
int[] name = new int[N + 1];
for(int i=1; i<=N; i++) {
name[i] = Integer.parseInt(br.readLine());
}
int[][] dp = new int[N + 1][M + 1]; // A는 몇 번째 이름인지, B는 현재 줄에서 어디까지 사용했는지
//초기화
for(int i=1; i<=N; i++) {
for(int j=1; j<=M; j++) {
dp[i][j] = Integer.MAX_VALUE;
}
}
dp[1][name[1]] = calSquare(M - name[1]);
ArrayList<Integer> list = new ArrayList<>();
list.add(name[1]);
for(int i=2; i<=N; i++) {
ArrayList nList = new ArrayList<>();
nList.add(name[i]);
for(int j=0; j<list.size(); j++) {
int len = list.get(j);
//이어 붙이는 경우
if(len + (1 + name[i]) <= M) {
int newLen = len + (1 + name[i]);
int newSquareV = calSquare(M - newLen);
if(i == N) {
//마지막 줄이라면 값에 포함 x
newSquareV = 0;
}
if(dp[i][newLen] == Integer.MAX_VALUE) {
//최초 초기화라면 list에 넣어주기
nList.add(newLen);
}
dp[i][newLen] = Math.min(dp[i][newLen], dp[i - 1][len] - calSquare(M - len) + newSquareV);
}
//새로운 줄에 쓰는 경우
int newSquareV2 = calSquare(M - name[i]);
if(i == N) {
//마지막 줄이라면 값에 포함 x
newSquareV2 = 0;
}
dp[i][name[i]] = Math.min(dp[i][name[i]], dp[i - 1][len] + newSquareV2);
}
list = nList;
}
int answer = Integer.MAX_VALUE;
for(int i=0; i<list.size(); i++) {
answer = Math.min(answer, dp[N][list.get(i)]);
}
System.out.println(answer);
}
static int calSquare(int v) {
return v * v;
}
}