Codeforces Round #813 (Div. 2) - Wonderful Permutation 링크
(2022.10.19 기준 Difficulty *800)
(Never cheat)

문제

1부터 n까지의 순열 p가 있을 때, 1~k번째 원소까지의 합이 최소가 되도록 p의 두 원소 교체 최소 횟수

알고리즘

합이 최소가 되게 교체하는 최소 횟수를 구해야 한다.
그리디하게 풀어나가보자.

풀이

순열 p는 수가 겹치지 않게 1부터 n까지 하나씩 들어 있다.
그러면 1~k번째 원소까지의 합이 최소가 되려면? 그 범위에 1부터 k까지의 수가 있을 때, 합이 최소가 된다.
그러면 1~k 범위에 1~k가 아닌 수가 들어 있으면, 범위 밖에 있는 1~k인 수와 교체를 해주면 되는데, 이를 쉽게 풀어내면, 1~k 범위에 1~k가 아닌 수의 개수가 교체 횟수가 된다.

코드

import sys; input = sys.stdin.readline

for _ in range(int(input())):
    n, k = map(int, input().split())
    arr = list(map(int, input().split()))
    answer = 0
    for a in arr[:k]: # k번째 까지 원소 검사
        if a > k: # 만약 원소가 k보다 크면
            answer += 1 # 범위 밖 1~k와 교체해야 하므로, 횟수 1 증가
    print(answer)

여담

풀이를 보면 굉장히 간단하고 쉬울 수 있는데, 의외로 바로 이런 풀이는 떠오르지 않던 문제.
contest 당시에는 k번째까지의 원소가 나온다고 상태를 담아둔 배열로 1부터 k까지 검사하면서 나오지 않은 상태면 answer += 1 해주는 방식을 썼는데, 뭐 비슷하긴 하지만 일을 두 번 했던 셈.