[백준 20186] 수 고르기 - python, js

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

 

💡문제 분석 요약

N개의 자연수가 좌우로 배열되어 있다. 여러분은 이 중 K개를 골라야 한다. 고를 때는 K개 모두를 한번에 골라야 한다.

여러분이 고른 수 각각에 대해서 그 수의 점수를 계산할 것이다. 점수는 자신의 수에서 자신의 왼쪽에 있는 수 중 선택된 수의 개수를 뺀 값이다. 이렇게 고른 수 각각에 그 점수를 계산한 후 전체점수는 계산된 점수들의 합이다. 여러분은 전체점수가 최대가 되도록 K개의 수를 골라야 한다.

예를 들어서, N = 5개의 자연수가 순서대로 2 3 1 2 1 로 주어지고, K = 3이라고 하자. 만약 첫 번째 2와 두 개의 1을 골랐다면, 각 수의 점수를 계산해서 나열하면 2 0 −1과 같다. 따라서 전체 점수는 1이다. 만약 첫 번째 2와 3, 그리고 두 번째 2를 고르고, 각 수의 점수를 계산해서 나열하면, 2 2 0과 같다. 따라서 전체점수는 4이다. 이 예에서 전체점수의 최댓값은 4이다.

N개의 자연수 배열과 양의 정수 K가 주어질 때, 전체점수의 최댓값을 출력하는 프로그램을 작성하시오.

 

💡알고리즘 설계

N개 중 K개를 고름

점수=자신의 값−왼쪽에 선택된 수의 개수

1. 큰 숫자부터 선택해야한다.
2. 왼쪽에 선택된 수의 개수는 점점 늘어난다.

⇒내림차순 정렬 후 K개만 선택한다.

1. 입력받은 숫자 리스트를 (입력받은 숫자, 숫자의 순서) 형태로 변환
2. 숫자 리스트를 숫자가 큰 순서대로 정렬 후 K 번째까지 자르기
3. answer에 해당 숫자를 더하고 이전에 선택된 숫자의 개수를 뺀다

 

💡코드

N, K = map(int, input().split())
numbers = list(map(int, input().split()))

nums_orders = []
for i in range(N):
    nums_orders.append((numbers[i],i))

sorted_numbers = sorted(nums_orders, reverse=True)
sorted_numbers=sorted_numbers[:K]
sorted_numbers.sort(key=lambda x : x[1])

checked_list=[]
answer=0

for num in sorted_numbers:
    answer+=num[0]
    for checked_num in checked_list:
        if checked_num<num[1]:
            answer-=1
    checked_list.append(num[1])

print(answer)

 

통과는 했는데 서브태스크 통과를 못해서 60점이 나왔다

굳이 3,2,2로 정렬 후 기존 리스트 순서대로 2,3,2로 재정렬 할 필요가 없는 것 같아서 바꿨다.

N, K = map(int, input().split())
numbers = list(map(int, input().split()))

sorted_numbers = sorted(numbers, reverse=True)[:K]

answer=0
count=0

for num in sorted_numbers:
    answer+=num-count
    count+=1

print(answer)

 

count가 점수=자신의 값−왼쪽에 선택된 수의 개수에서 왼쪽에 선택된 수의 개수이다..

const readline = require("readline");

(async () => {
  let rl = readline.createInterface({ input: process.stdin });
  const input = [];
  let inputCount = 2;
  for await (const line of rl) {
    input.push(line);
    inputCount--;
    if (inputCount == 0) rl.close();
  }
  const [N, K] = input[0].split(" ").map(Number);
  const numbers = input[1].split(" ").map(Number);

  const sortedNumbers = numbers.sort((a, b) => b - a).slice(0, K);

  let answer = 0;
  let count = 0;

  for (const num of sortedNumbers) {
    answer += num - count;
    count++;
  }

  console.log(answer);
})();

💡 느낀점 or 기억할 정보

쉽게 풀기가 어렵다

쉽게 풀기 위해 어렵게 푸는 연습을 해야하는 것이 웃긴 것 같다