BOJ 백준 6208 Cow Roller Coaster

문제 : https://www.acmicpc.net/problem/6208

 

[ 문제 요약 ]

- 길이 L 짜리 직선 트랙 위에, N 개의 부품 중에서 선택해 롤러코스터를 만든다.

- 롤러코스터는 0에서 시작해서 L에서 끝나야 하고, 부품은 Xi 위치에서 시작하고 길이 Wi 만큼 차지한다. 시작 위치는 중복될 수 있다.

- 각 부품은 한 번씩만 사용하며, 부품마다 재미 Fi, 비용 Ci를 가지고 있다.

- 총예산 B를 초과하지 않고, 부품을 연결하면서 재미의 합을 최대화하여 재미의 합을 출력한다.

 

 

[ 테스트 케이스 설명 ]

5 6 10 // 트랙의 길이 L=5, 부품 개수 N=6, 예산 B=10
0 2 20 6 // x=0, 길이 w=2, 재미 f=20, 비용 c=6 → [0~2]까지 설치 가능
2 3 5 6  // x=2, 길이 w=3, 재미 f=5, 비용 c=6 → [2~5]까지 설치 가능
0 1 2 1  // x=0, 길이 w=1, 재미 f=2, 비용 c=1 → [0~1]까지 설치 가능
1 1 1 3  // x=1, 길이 w=1, 재미 f=1, 비용 c=3 → [1~2]까지 설치 가능
1 2 5 4  // x=1, 길이 w=2, 재미 f=5, 비용 c=4 → [1~3]까지 설치 가능
3 2 10 2 // x=3, 길이 w=2, 재미 f=10, 비용 c=2 → [3~5]까지 설치 가능
//답 17

 

 

[ 문제 풀이 ]

시작 위치(x)가 중복될 수 있고, 시작 위치가 같을 때, 끝나는 길이가 다를 수 있으므로 관련 내용을 단순하게 바꿔야 한다.

 

시작 위치를 기준으로 데이터를 저장하는 list를 선언하여 거기에 부품 길이, 재미 점수, 비용을 저장하는 방식으로 자료구조를 만들어 문제를 해결한다. dp 형식은 아래와 같이 만든다.

 

dp[현재 길이][현재 길이까지 만드는데 드는 비용] = 재미의 최댓값

 

그리고 dp를 구해나갈 때, 현재 진행 중인 길이와 현재까지의 비용을 통해 나중을 계산해 나간다.(코드를 통해 이해 가능)

 

이때, 현재 길이와 비용이 유효한 값이 아닐 경우 계산하면 안 되고, 유효한 값일 때만 계산해야 한다. 이를 구분하기 위해 여러 가지 방법이 있다. dp 배열을 -1로 전부 초기화하여 음수인 경우는 유효하지 않은, 즉, 현재까지 값을 계산한 적이 없는 값으로 보고 스킵 하는 방법이 있고, 단순히 dp[0][0]을 1로(재미의 시작 값이 1인 것) 마킹하여 유효한 값을 0초과인 것으로 계산하는 방법도 있다.

 

나는 dp[0][0] 을 1로 마킹하여 유효한 값은 0 초과인 것으로 구분하도록 구현했다. 이렇게 하면 추후 재미의 최댓값 출력 시 -1을 해서 원래대로 값을 보정해 주어야 한다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
class Node
{
	int w,f,c;
	Node(int w,int f, int c)
	{
		this.w=w;// 부품길이
		this.f=f;// 재미점수
		this.c=c;// 비용
	}
}
class Main{
	public static void main(String[] args)throws Exception{
		BufferedReader	br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int L	= Integer.parseInt(st.nextToken());// 롤러코스터 길이L(1<=1,000)
		int N	= Integer.parseInt(st.nextToken());// 부품의 개수N(1<=10,000)
		int B	= Integer.parseInt(st.nextToken());// 쓸수있는 예산B(1<=1,000)
		ArrayList<Node> list[] = new ArrayList[L + 1];
		
		for(int i=0; i<=L; i++)
			list[i] = new ArrayList<>();
		
		for(int i=0; i<N; i++)
		{
			st = new StringTokenizer(br.readLine());
			int x	= Integer.parseInt(st.nextToken());// 시작위치X(0<=L-W)
			int w	= Integer.parseInt(st.nextToken());// 부품길이W(1<=L)
			int f	= Integer.parseInt(st.nextToken());// 재미점수F(1<=1,000,000)
			int c	= Integer.parseInt(st.nextToken());// 비용C(1<=1,000)
			list[x].add(new Node(w, f, c));
		}
		
		// dp[위치][비용] = 최대 재미
		int dp[][] = new int[L + 1][B + 1];
		
		dp[0][0] = 1;// 유효한 값을 마킹하여 0초과인 경우만 연산을 하도록 하기 위한 조치
		
		for(int l=0; l<=L; l++)
		{
			for(int b=0; b<=B; b++)
			{
				if(dp[l][b] == 0)// 유효하지 않으면 스킵
					continue;
				
				for(Node now : list[l])
				{
					int nextLeng = l + now.w;
					int nextCost = b + now.c;
					if(nextLeng <= L && nextCost <= B)
						dp[nextLeng][nextCost] = Math.max(dp[nextLeng][nextCost], dp[l][b] + now.f);
				}
			}
		}
		
		int res = 0;
		
		for(int c=0; c<=B; c++)
			res = Math.max(dp[L][c], res);
		
		if(res > 0)
			System.out.print(res - 1);// 처음 dp[0][0]을 1로 마킹했으므로 -1을하여 원래 값으로 복구
		else
			System.out.print(-1);
	}
}

 

 

list에 시작 위치에 따른 나머지 값(비용,길이,재미)들을 담는다.

 

그리고 가장 바깥 for 문을 길이로 둠으로써 길이에 따른 노드를 효율적으로 불러올 수 있도록 하였다. (Node now : list[l])

 

그리고 현재 길이(l)와 현재까지 비용(b)을 통해 미래의 길이(nextLeng), 미래의 비용(nextCost)을 구하고, 최대 재미를 갱신한다.(dp[nextLeng][nextCost] = Math.max(dp[nextLeng][nextCost], dp[l][b] + now.f))

 

처음에 설명한 현재 길이와 현재 비용을 통해 나중을 계산해나간다는 것이 이 의미이다.

 

이렇게 L까지 계속 갱신해나가면 dp[L]에는 비용에 따른 최대 재미가 담겨있을 것이기 때문에 for 문으로 전부 탐색하면서 가장 큰 재미 값(res)을 구하여 출력해 주면 된다.

 

결과 출력 시 처음에 최대 재미의 유효한 값을 1부터 시작하였으므로 res 출력 시 -1을 해야 정상적인 최대 재미 값이 된다.