99클럽 코테 스터디 27일차 TIL

비기너

문제

11557번: Yangjojan of The Year

# 정렬

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

풀이

학교 별로 술 소비량이 주어질 때 술 소비량이 최대인 학교를 구하는 문제이다.

School 객체를 만들어서 학교 이름과 술 소비량을 저장한다.

School 배열에 주어진 값들을 저장하고 이를 술 소비량을 기준으로 정렬한다.

술 소비량이 가장 많은 학교의 이름을 출력한다.

코드

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

class School {
	int l;
	String s;

	public School(String s, int l) {
		this.s = s;
		this.l = l;
	}
}

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int t = Integer.parseInt(br.readLine());

		while (t-- > 0) {
			int n = Integer.parseInt(br.readLine());
			School[] a = new School[n];
			for (int i = 0; i < n; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				String s = st.nextToken();
				int l = Integer.parseInt(st.nextToken());
				a[i] = new School(s, l);
			}
			Arrays.sort(a, (s1, s2) -> Integer.compare(s1.l, s2.l));
			bw.write(a[a.length - 1].s + "\n");
		}

		bw.flush();
		bw.close();
	}
}

미들러

문제

11722번: 가장 긴 감소하는 부분 수열

#동적계획법

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

풀이

수열에서 가장 긴 감소하는 부분 수열의 길이를 구하는 문제이다.

동적계획법을 이용하기 위해 각 수에서 끝나는 감소하는 부분 수열의 길이를 배열에 저장한다.

n번째 수에서 끝나는 감소하는 부분 수열의 길이는 1 ~ n - 1의 감소하는 부분 수열의 길이 중 최댓값 + 1로 구할 수 있다. 

(단 a[n] < a[i], 1 <= i <= n - 1)

따라서 1부터 시작해서 n까지 반복을 통해 만든 모든 감소하는 부분 수열의 길이를 저장한 배열에서 최댓값을 찾아서 출력하면 된다.

코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		int[] a = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++)
			a[i] = Integer.parseInt(st.nextToken());

		int[] d = new int[n];
		d[0] = 1;
		int ans = 1;
		for (int i = 1; i < n; i++) {
			d[i] = 1;
			for (int j = 0; j < i; j++) {
				if (a[j] > a[i])
					d[i] = Math.max(d[i], d[j] + 1);
			}
			ans = Math.max(ans, d[i]);
		}

		bw.write(ans + "");
		bw.flush();
		bw.close();
	}
}

챌린저

문제

1446번: 지름길

# 동적계획법

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

풀이

고속도로를 통과할 때 거리의 최솟값을 구하는 문제이다.

n인 지점까지의 거리는 n - 1까지의 거리와 지름길로 연결된 부분의 거리에 따라 결정된다.

따라서 동적계획법을 이용해서 각 지점까지의 거리를 저장하고 이를 바탕으로 다음 지점의 거리를 구한다.

코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int d = Integer.parseInt(st.nextToken());
		int[][] a = new int[n][3];
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 3; j++)
				a[i][j] = Integer.parseInt(st.nextToken());
		}

		int[] dist = new int[d + 1];
		for (int i = 0; i <= d; i++)
			dist[i] = i;

		for (int i = 1; i <= d; i++) {
			dist[i] = Math.min(dist[i], dist[i - 1] + 1);
			for (int j = 0; j < n; j++) {
				if (a[j][1] == i)
					dist[i] = Math.min(dist[i], dist[a[j][0]] + a[j][2]);
			}
		}

		bw.write(dist[d] + "");
		bw.flush();
		bw.close();
	}
}