[Baekjoon] 10571_다이아몬드

문제(출처: https://www.acmicpc.net/problem/10571)

---

< 다이아몬드 >

 

문제 풀이 

 

다이아몬드를 살펴보며 현재 다이아몬드가 앞에 다이아몬드보다 중량이 높고, 선명도가 낮은지 확인한다. 

 

my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class _10571_ { // 다이아몬드
	static class Pair {
		double w, c;

		public Pair(double w, double c) {
			this.w = w;
			this.c = c;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int t = Integer.parseInt(bf.readLine());

		for (int i = 0; i < t; i++) {
			int n = Integer.parseInt(bf.readLine());

			Pair arr[] = new Pair[n];
			int dp[] = new int[n];

			for (int j = 0; j < n; j++) {
				st = new StringTokenizer(bf.readLine());
				arr[j] = new Pair(Double.parseDouble(st.nextToken()), Double.parseDouble(st.nextToken()));
				dp[j] = 1;
			}

			for (int j = 1; j < n; j++) {
				for (int k = 0; k < j; k++) {
					if (arr[k].w < arr[j].w && arr[k].c > arr[j].c) {
						dp[j] = Math.max(dp[j], dp[k] + 1);
					}
				}
			}

			int result = 0;
			for (int j = 0; j < n; j++) {
				result = Math.max(result, dp[j]);
			}
			bw.write(result + "\n");
		}
		bw.flush();
	}

변수)
t : 테스트케이스 개수
n : 다이아몬드의 정보 개수
arr : 다이아몬드 정보
dp : 가치가 높아지는 다이아몬드 수
result : 가치가 높아지는 부분열 중 최장의 길이 

 

테스트케이스 개수를 입력받는다. 테스트 케이스 수만큼 다음 과정을 반복한다.

 

1) 다이아몬드 정보의 개수를 입력받는다.

2) 다이아몬드 정보의 개수만큼 다이아몬드 정보를 입력받아 arr에 저장하고, dp를 1로 초기화한다.

3) 배열을 탐색하며 현재 다이아몬드가 앞에 다이아몬드보다 중량이 높고, 선명도가 낮다면 dp 값을 업데이트한다.

4) 최종 dp를 살펴보며 최댓값을 구해 출력한다. 

---

---