1332. 풀자

문제가 궁금하시다면, 아래의 링크를 클릭해주세요!
문제 보러 가기

접근 과정

1번 문제는 반드시 푼다는 조건 하에, 문제를 푸는 방법에는 어떤 것이 있을까?

• N + 1번 문제 순서로 풀어나간다. ex > 2, 3, 4, 5 ...
• N + 2번 문제 순서로 풀어나간다. ex > 3, 5, 7, 9 ...
• N + 1, N + 2번 문제를 무작위로 풀어나간다. ex > 2, 4, 6, 7 ...

첫 번째, 두 번째 경우에는 크게 고려할 부분이 없지만, 문제가 되는 경우는 N + 1번 문제와 N + 2번 문제를 순서 없이 무작위로 풀어나가게 되는 세 번째 케이스다.

이 경우, 특정한 규칙으로 정의되지 않는다. 그렇다면 여기에서 무엇을 유추할 수 있을까?

• 모든 경우를 고려해야 한다는 것이다!!

이를 바탕으로 주어진 문제의 수 N까지의 범위에 대해 모든 경우를 조사하는 브루트포스 알고리즘을 고려해야 한다고 생각하게 되었고, 1부터 시작하는 임의의 수 Nx에 대해 매 순간 N + 1, N + 2를 고려하기 위해서 재귀를 사용하기로 결정하였다.

재귀 사용시, 탈출 조건은?

재귀를 사용한다면, 탈출 조건을 반드시 명시해야 한다. 이 문제에서는 어떤 경우가 탈출 조건에 해당될까?

• 재귀 함수에 전달되는 N이 문제에서 제시된 총 문제 수 N 이상인 경우
  • 재귀를 거듭하며, 중첩되는 재귀 함수에는 N + 1이나, N + 2가 인자로 전달된다.
  • 이 때의 인덱스 N은 문제에서 최초에 제시하는 문제 수 N보다 클 수 없다!
• 재귀 함수에 전달되는 푼 문제 수를 나타내는 자연수 k가 현재까지의 푼 문제 수 최솟값보다 커지는 경우
  • 출력해야 하는 것은, 만족도 최댓값 - 최솟값이 한도 V 이상이라는 조건을 만족할 때의 최소 문제 수이다!
  • 재귀 함수에 전달되는 푼 문제 수 k가 현재까지 저장된 최소 문제 수보다 커지는 경우, 더 이상 연산을 수행하는 의미가 없다.

그 외에 고려할 사항은?

재귀 함수 호출 이전에, 주어진 문제 만족도 리스트에서 최댓값과 최솟값의 차가 V 미만인지 확인해야 한다!

두 값의 차가 V 미만이라면, N + 1 순서대로 모든 문제를 풀어도 최대 만족도와 최소 만족도의 차가 V 미만이기 때문이다.

• 이 경우, 풀어야 하는 문제 수는 N이기 때문에 재귀 함수를 호출하지 않고 바로 N을 출력한다!

정리하면?

• 주어지는 문제의 최대 만족도 - 최소 만족도가 V 미만이라면, N을 출력한다.
• 그 외의 경우는 재귀를 사용해, 모든 경우를 고려한다.
  • 푼 문제 수가 현재까지 저장된 문제 수 최솟값보다 커지거나,
  • 재귀 함수에 전달되는 문제 배열에서의 인덱스가 문제 수 N 이상이 되는 경우는 탈출한다.
  • 그 외의 경우, 문제의 만족도를 기준으로 최솟값과 최댓값을 갱신해가면서, 만족도간의 차가 V 이상이 되는 경우의 최소 문제 수를 저장한다!

풀이

import sys
sys.setrecursionlimit(10**5)

def calc(problem_idx, min_V, max_V, solved_number):
    global ans

    # 주어진 문제 수를 넘어가는 경우
    if problem_idx >= N:
        return

    # 현재까지 푼 문제 수가 현재까지의 최솟값보다 커지는 경우 -> 답이 될 수 없음
    if solved_number > ans:
        return

    # 현재 시점의 문제를 기준으로, 최댓값 - 최솟값 갱신
    min_V = min(min_V, success[problem_idx])
    max_V = max(max_V, success[problem_idx])

    # 현재 만족도 최댓값 - 최솟값의 차가 V 이상이라면, 더 이상 풀지 않아야 함
    if max_V - min_V >= V:
        ans = min(ans, solved_number)
        # ans = solved_number
        return

    # 위의 조건들을 통과했다면, 풀 수 있는 문제가 남은 경우 -> N + 1번을 풀거나, N + 2번을 풀거나
    # N + 2번 문제 풀이
    calc(problem_idx + 2, min_V, max_V, solved_number + 1)
    # N + 1번 문제 풀이
    calc(problem_idx + 1, min_V, max_V, solved_number + 1)

    
N, V = map(int, input().split())
success = list(map(int, input().split()))
ans = N

# 최초에 주어진 문제들에서 최댓값 - 최솟값의 차가 이미 V 미만인 경우라면?
# 전부 풀어도 만족도의 차는 V보다 작다 -> 전부 풀게 된다 -> 바로 N 출력
if max(success) - min(success) < V:
    print(ans)
else:
    calc(0, 1000, -1000, 1)
    print(ans)

읽어주셔서 감사합니다!