[Baekjoon] 6193_Hungry Cows

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

---

< Hungry Cows >

 

문제 풀이 

 

dp를 사용하여 직전에 먹이를 먹은 소보다 번호가 더 큰 소만 먹이를 먹여 최대 먹이를 줄 수 있는 소의 수를 구한다.

 

my solution (Java)

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

public class _6193_ { // Hungry Cows

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

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

		int arr[] = new int[n];
		int idx = 0;
		int range = n / 20;
		if (n % 20 != 0) {
			range += 1;
		}

		for (int i = 0; i < range; i++) {
			st = new StringTokenizer(bf.readLine());
			while (st.hasMoreTokens()) {
				arr[idx++] = Integer.parseInt(st.nextToken());
			}
		}

		int dp[] = new int[n];
		for (int i = 0; i < n; i++) {
			dp[i] = 1;
		}

		for (int i = 1; i < n; i++) {
			for (int j = 0; j < i; j++) {
				if (arr[j] < arr[i]) {
					dp[i] = Math.max(dp[i], dp[j] + 1);
				}
			}
		}

		int result = 0;
		for (int i = 0; i < n; i++) {
			result = Math.max(result, dp[i]);
		}

		System.out.println(result);
	}

변수)
n : 입력값 
arr : 소 번호
dp : 먹이를 줄 수 있는 소의 수

 

n을 입력받는다. 소 번호는 한 줄에 20개씩 입력되므로 20으로 나누어 떨어진다면 n/20 만큼, 나누어 떨어지지 않는다면 n/20 +1만큼 반복하여 입력받아 arr에 저장한다. dp 초기값을 다 1로 저장한다. 배열을 전체 탐색하며 현재 소 번호보다 앞에 있는 소 번호가 작다면 +1 한 값과 현재 값 중 최댓값으로 업데이트한다.

 

최종 dp 배열을 탐색하며 최댓값을 출력한다. 

---

---