[Python] 5526번 ダーツ (Darts)

 

 

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

5526번: ダーツ (Darts)

---

 

23/12/29

 

 

중간에서 만나기(MITM) 연습 문제로 아주 적절한 문제이다. 

---

 

첫번째 문제 접근 방식:

 

 

문제를 해석하자면 아래와 같다.

 

화살을 과녁을 향해 네 자루 던질 수 있다. 반드시 4개를 다 던질 필요는 없으며, 하나도 던지지 않아도 된다.
과녁은 $N$개의 부분으로 구분되어 있으며, 각 부분에는 점수 $P_1, P_2, \cdots , P_N$이 쓰여있다.
화살이 꽃힌 곳의 점수를 모두 합한 값 $S$가 기본 점수가 된다.
만약 $S$가 미리 정해진 어떤 점수 $M$보다 클 경우, 최종 점수는 $0$점이 된다.
그렇지 않은 경우에는 $S$가 그대로 최종 점수가 된다.

과녁에 적혀 있는 점수가 주어지고 $M$값이 주어질 경우, 얻을 수 있는 최대의 최종 점수를 구하자.
$N$의 제한은 $1,000$까지이다. 

 

처음에 접근 했던 방식은, 이전에 접근 했던 문제(2295번)처럼 집합을 사용한 접근 방법이었다.

 

2024.01.04 - [알고리즘/백준 문제 풀이] - [Python] 2295번 세 수의 합

[Python] 2295번 세 수의 합

 

화살을 쏘지 않는 경우도 있으므로, 점수가 겹치는 부분이 상당히 많을 것이라고 생각했고 집합으로 구현하면 시간 초과를 받지 않을 것이라고 생각했었다.

 

하지만 집합을 두 개를 구성하는 데에 있어서, 이전에 만들었던 집합으로 다음 집합을 만드니 시간 초과를 받을 수 밖에 없었다.

 

이 접근 방식은 $N \leq 100$인 경우에는 잘 통과해서 부분 점수 20점을 받을 수 있었다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 5526번 ダーツ (Darts)
# 분할 정복
'''
당신은 아래 규칙에 따라 다트 게임을 하게 되었다.
(당신은 화살을 과녁을 향해) 네 자루까지 던질 수 있다.
반드시 네 개 모두를 던질 필요는 없고, 한 개도 던지지 않아도 된다
과녁은 N개의 부분으로 구분되어 있으며, 각각의 부분에 점수 P1,· · · , PN이 쓰는가 되어 있다.
화살이 꽂힌 장소의 점수 합계 S가 당신의 득점의 기초가 된다.
S가 미리 정해진 어떤 점수 M 이하의 경우는 S가 그대로 당신의 득점이 된다.
그러나 S 이 M을 넘을 경우 당신의 득점은 0점이 되다
과녁에 적혀 있는 점수와 M의 값이 주어졌을 때, 당신이 얻을 수 있는 최대 점수를 찾는 프로그램을 만들어라.
'''
import sys
input = sys.stdin.readline

N, M = map(int, input().rstrip().split())
P = list(int(input()) for _ in range(N)) + [0]
num_set = set()
num_set.add(0)
for i in range(N+1):
    for j in range(N+1):
        if P[i]+P[j] <= M:
            num_set.add(P[i]+P[j])
num_set2 = set(i+j if i+j <= M else 0 for i in num_set for j in num_set)
print(max(num_set2))

---

 

두번째 문제 접근 방식:

 

 

두번째 접근 방식은 의도대로 MITM을 진행했다.

 

두 그룹을 만들었는데 사실 이 두 그룹은 동일한 그룹이다.

 

즉, 합 배열 하나만 만들고 그걸 그냥 정렬하면 충분했다.

 

이때 중복을 제거 하기 위해 집합에다 넣어주고 정렬된 배열을 만들었다.

 

이후 투 포인터로 탐색을 진행했다.

 

$M$을 넘어갈 경우, 합을 더 작도록 만들기 위해 end포인터를 1만큼 줄였다.

 

그러지 않으면 start포인터를 1만큼 늘렸다.(합을 더 크도록 만들기 위해)

 

그 과정 중에서 조건을 만족시키는 최댓값이 갱신될 수 있다면 갱신시켜주었다.

 

전체적인 흐름은 이전에 풀었던 MITM 연습 문제와 거의 동일하다.

 

2024.01.02 - [알고리즘/백준 문제 풀이] - [Python] 7453번 합이 0인 네 정수

[Python] 7453번 합이 0인 네 정수

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 5526번 ダーツ (Darts)
# mitm, 투포인터
'''
당신은 아래 규칙에 따라 다트 게임을 하게 되었다.
(당신은 화살을 과녁을 향해) 네 자루까지 던질 수 있다.
반드시 네 개 모두를 던질 필요는 없고, 한 개도 던지지 않아도 된다
과녁은 N개의 부분으로 구분되어 있으며, 각각의 부분에 점수 P1,· · · , PN이 쓰는가 되어 있다.
화살이 꽂힌 장소의 점수 합계 S가 당신의 득점의 기초가 된다.
S가 미리 정해진 어떤 점수 M 이하의 경우는 S가 그대로 당신의 득점이 된다.
그러나 S 이 M을 넘을 경우 당신의 득점은 0점이 되다
과녁에 적혀 있는 점수와 M의 값이 주어졌을 때, 당신이 얻을 수 있는 최대 점수를 찾는 프로그램을 만들어라.
'''
import sys
input = sys.stdin.readline

N, M = map(int, input().rstrip().split())
P = list(int(input()) for _ in range(N)) + [0]
num_set = set()
num_set.add(0)
for i in range(N+1):
    for j in range(N+1):
        if P[i]+P[j] <= M:
            num_set.add(P[i]+P[j])
num_li = sorted(num_set)
start, end = 0, len(num_li)-1
max_val = num_li[start]+num_li[end]
while start <= end:
    val = num_li[start]+num_li[end]
    if val > M:
        val = 0
        end -= 1
    elif val <= max_val:
        start += 1
    else:
        max_val = val
        start += 1
print(max_val)