[BAEKJOON]17224 APC는 왜 서브태스크 대회가 되었을까?

 

문제 요약

• 알고리즘 분류:  구현, 수학, 그리디
• 난이도: Bronze1
• 문제내용:
  • 첫 줄에 문제의 개수 N, 현정이의 역량 L, 현정이가 대회중에 풀 수 있는 문제의 최대 개수 K가 주어진다.
  • 어려운 문제 풀면 140점, 쉬운 문제 풀면 100점을 얻는다.
  • 어려운 문제나 쉬운 문제중 현정이 역량이 안되면 풀수가 없다.
  • 얻는 점수 최대값을 출력해라
• 사이트: https://www.acmicpc.net/problem/17224

17224번: APC는 왜 서브태스크 대회가 되었을까?

문제풀이

 이번 문제는 그리디인데 그리디에 관련된 자세한 아래 사이트에서 보면 된다.

https://jih3508.tistory.com/70 

[알고리즘 이론] 그리디(Greedy)

 이번 문제에서는 2가지로 푸는 방법으로 설명 할것이다. 하나는 배열로 구현 하는 것과 다른 하나는 입력받을때 연산해서 계산 하는 방식으로 푸는 법을 설명 할것이다. 첫번째로 배열로 구현하는 순서는 아래와 같다.

1. easy, hard문제를 리스트나 배열에 저장한다.
2. hard문제 기준으로 오름차순으로 정렬한다.
3. 각 문제를 푸는데 풀때 아래와 같은 조건으로 문제를 푼다.
   - 어려운 문제 풀 수 있으면 어려운 문제를 푼다.
   - 어려운 문제를 못 풀경우 쉬운 문제를 푸는데 쉬운 문제도 역량이 되면 푼다.
   - 문제 풀때 마다 최대 풀 수 있는 개수를 줄인다.

 두번째로 연산 해서 푸는 방법인데 구현 하는 순서는 아래와 같다.

1. 쉬운 문제, 어려운 문제 변수를 0으로 초기화 하고 각 입력 받을때 마다.  아래같은 조건으로 쉬운 문제, 어려운 문제 개수를 추가 한다.

  - 어려운 문제 풀 수 있으면 어려 운 문제를 추가 한다.

  - 어려운 문제를 풀 수 있는 역량이 안되면 쉬운 문제를 추가 하는데 쉬운 문제도 풀 수 있는 역량이 되면 추가 한다.

2. 어려운 문제와 최대 풀 수 있는 것중 적은 것을 계산 한다.

3. 어려운 문제가 최대 풀 수 있는 문제보다 미만일 경우 쉬운 문제와 (최대 풀 수 있는 문제 - 어려운 문제)중 가장 적을 것을 계산한다.

 

 이러한 구현 과정을 통해 간편하게 2가지 방법으로 문제를 풀 수 있다. 위의 순서대로 진행하면 문제를 해결하는 데 큰 어려움이 없을 것으로 예상된다. 

 

Code

Python

리스트로 Greedy 구현

 sorted(tests, key=lambda x: x[1]) : 2차원 이상 배열 정렬하는 것인데 정렬 하는 기준을 각 열의 1번째 인덱스 기준으로 정렬 한다.  

N, L, K = map(int, input().split())
tests = [list(map(int, input().split())) for _ in range(N)]

# 문제 어려운 순으로 오름차순 정렬
tests = sorted(tests, key=lambda x: x[1])

result = 0 # 결과 값 변수

# 문제 풀때 마다 최대 문제 푸는 수를 차감한다.
for test in tests:
    # 최대 풀수 있는 문제가 초과 되면 반복문에서 빠져 나온다.
    if K == 0:
        break
    # 어려운 문제 풀수 있는 경우
    elif L >= test[1]:
        result += 140
        K -= 1
    elif L >=test[0]:
        result += 100
        K -= 1

print(result)

계산해서 푸는 방법

N, L , K = map(int, input().split())

easy, hard = 0, 0

for _ in range(N):
    sub1, sub2 = map(int, input().split())
    if L >= sub2:
        hard += 1
    elif L>= sub1:
        easy += 1

# hard 문제
result = min(K, hard) * 140

# easy 문제
if(K > hard):
    result += min(K-hard, easy) * 100

print(result)

Java

배열로 Greedy 구현

Arrays.sort(tests, Comparator.comparing((int[] test) -> test[1]));

- 배열 정렬 하는 Comparator.comparing이라는 정렬 기준을 정의 하는 메소드 이다.

- (int[] test) -> test[1] 람다식으로 정렬 기준을 각 열의 1번째 인덱스 기준으로 정렬 한다. 

- 역순으로 정렬 하고 싶으면 Comparator.comparing((int[] test) -> test[1]).reversed()  뒤 reversed() 메소드를 붙이면 된다.

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

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int L = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());

		int sub1, sub2;

		int[][] tests = new int[N][2];
		for(int i = 0; i < N; i++){
			st = new StringTokenizer(br.readLine());
			sub1 = Integer.parseInt(st.nextToken());
			sub2 = Integer.parseInt(st.nextToken());
			tests[i][0] = sub1;
			tests[i][1] = sub2;
		}
		
		//배열 어려문제 위주로 오름 차순 정렬
		Arrays.sort(tests, Comparator.comparing((int[] test) -> test[1]));

		int result = 0; // 결과 값 변수
		// 문제 풀때 마다 최대 문제 푸는 수를 차감한다.
		for(int[] test: tests){
			// 최대 풀수 있는 문제가 초과 되면 반복문에서 빠져 나온다.
			if(K == 0) break;
			// 어려운 문제 풀수 있는 경우
			else if(L >= test[1]){
				result += 140;
				K--;
			// 어려운 문제를 못풀 경우 쉬운 문제 풀 수 있는 경우	
			}else if(L >= test[0]){
				result += 100;
				K--;
			}
		}

		System.out.println(result);
	}

}

계산해서 푸는 방법

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

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int L = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());

		int sub1, sub2;
		int easy = 0;
		int hard = 0;

		for(int i = 0; i <N; i++){
			st = new StringTokenizer(br.readLine());
			sub1 = Integer.parseInt(st.nextToken());
			sub2 = Integer.parseInt(st.nextToken());

			if (L >= sub2){
				hard++;
			} else if (L >= sub1) {
				easy++;
			}
		}

		int result = Math.min(K, hard) * 140;

		if(hard < K) {
			result += Math.min(K - hard, easy) * 100;
		}

		System.out.println(result);
	}

}