백준 6144 Charm Barcelet

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

다국어문제
사실 냅색이란걸 알고풀어서 별 의미가없는거같긴하지만

w와 d를 이용한 계산 그리고 max치 찾기 이전 냅색문제 유형과 똑같다

여기서는 문제를풀면서 조건이 좀더 타이트할수도있다고생각했다.

일단 시간초과가안날꺼같아서 기존의방법대로 풀었고

좀더 좋게 변경하자면 hashmap으로 만들어서 중복체크를 해주고 진행하면될꺼같지만 굳이 안해도 되긴한다..

간단한 냅색이라 메인아이디어는 없고 바로 코드로

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

public class CharmBracelet {

	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int[] w = new int[N];
		int[] d = new int[N];
		int[] result = new int[M+1];
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			w[i] = Integer.parseInt(st.nextToken());
			d[i] = Integer.parseInt(st.nextToken());
		}
		
		for(int i=0;i<N;i++) {
			for(int j= M;j>=w[i];j--) {
				result[j] = Math.max(result[j], result[j-w[i]]+d[i]);
			}
		}
		
		System.out.println(result[M]);

	}

}