[Java] 백준 1049번 기타줄

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

1049번: 기타줄

문제 설명

• N : 끊어진 기타 줄 개수, M : 기타 줄 브랜드
• 6개의 패키지 가격과 낱개의 가격이 주어질 때 N개의 기타 줄을 사기 위해 필요한 최소 비용
• 1 <=N <=100, 1 <=M <=50
• 0 <=가격 <=1000

 

처음에 기타 줄을 같은 브랜드끼리 구매해야 하는 줄 알고 각 브랜드의 최소 비용을 구한 다음 또다시 M개의 브랜드 중 최소 비용을 계산해주었다.

하지만 어떤 브랜드의 기타 줄을 구매하는가는 상관없이 최소비용만 구하면 되는 문제이므로 결국 패키지를 샀을 때의 샀을 때의 최소금액과 낱개로 샀을 때의 최소금액 두 금액만 가지고 총  N개의 기타 줄을 사기 위해 필요한 최소 비용을 계산해주면 된다. 

 

dp [N] : N개의 기타 줄을 구입했을 때 최소비용

 

dp [N]을 구하는 경우의 수는 다음과 같다.

1. 패키지로 구매할 경우
2. 낱개로 구매하는 경우
3. 패키지 + 낱개로 구매하는 경우

 

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		
		int N = s.nextInt();
		int M = s.nextInt();
		int Min = 100000;
		
		int m[][]=new int[M+1][3]; //각 브랜드 패키지 가격과 낱개 가격
		int dp[]=new int[N+1];
		
		for(int i=1;i<=M;i++) {
			for(int j=1;j<3;j++) {
				m[i][j]=s.nextInt();
			}
		}
		
		int minP=1000;
		int minO=1000;
		
		for(int j=1;j<=M;j++) {
			minP=Math.min(minP,m[j][1]); //패키지 최소 금액
			minO=Math.min(minO,m[j][2]); //낱개 최소 금액
		}
	
		for(int i=1;i<=N;i++) {
				
				dp[i]=Math.min(((i/6)+1)*minP,dp[i-1]+minO);
				dp[i]=Math.min(dp[i],(i/6)*minP+(i%6)*minO);
				
		}
	
		System.out.print(dp[N]);
	}
	
}