[SWEA] 2115. [모의 SW 역량테스트] 벌꿀채취
📚 문제
📖 풀이
가로로 연속되게 고를 수도 있는데 제출할 때 가로로 고르게 짜면 fail 뜬다. 제출 검증 케이스를 잘못 만들어 놨는지, 각 줄에서 최대 값만 뽑으면 그게 답이 된다.
일단 같은 라인에서 뽑아도 가능하게 코드를 작성했다.
먼저 현재 인덱스 기준 m의 가장 왼쪽을 차지하고 m칸 중 최대 비용을 배열에 적어준다.
그림으로 보면
네모칸에 있는 값들 중 가장 큰 값을 동그라미에 적어주는 것이다.
이처럼 작성한 후 줄 별로 최댓값을 뽑는다.
그리고 최댓값을 정렬시키고 가장 큰 값과 두번째로 큰 값을 고르면, 줄 별로 최댓값을 뽑는 코드는 완성이다.
한 줄에 2개 뽑을 수 있는 경우도 확인하기 위해, 최댓값을 정렬한 배열에서 가장 큰 값과 같은 값들은 같은 라인에서 최댓값을 갱신시킬 다른 값이 있는지 확인해준다.
그러면 다음과 같은 테스트 케이스도 정상적으로 나온다.
1
4 2 10
1 1 1 1
3 3 3 3
1 1 1 1
1 1 1 1
결과 : 36
📒 코드
def recur(cur, total, money): # 구간에서 최대의 액수 구하기
global max_money
if total > c: # c보다 크면 리턴
return
if cur == m: # 구간을 다 확인했으면 최댓값 갱신
max_money = max(max_money, money)
return
# 조합으로 (선택하는 경우와, 선택하지 않는 경우)
recur(cur + 1, total, money)
recur(cur + 1, total + temp[cur], money + temp[cur] ** 2)
t = int(input())
for tc in range(1, 1 + t):
n, m, c = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
moneys = [[0] * n for _ in range(n)]
for i in range(n): # 각 구간별 최댓값을 맨 왼쪽 인덱스에 담아준다.
for j in range(n - m + 1):
cnt = 0
max_money = 0
temp = arr[i][j:j + m] # 구간을 배열에 담아 재귀함수로 최대 액수를 찾아준다.
recur(0, 0, 0)
moneys[i][j] = max_money
max_money = []
max_result = 0
for i in range(n): # 각 라인별로 최댓값을 뽑는다.
max_money.append((max(moneys[i]), i))
max_money.sort() # 최댓값을 정렬한다.
max_result = max_money[-1][0] + max_money[-2][0] # 정렬하여 큰 순서로 2개 뽑아 더해준다.
for i in range(1, n + 1):
if max_money[-i][0] != max_money[-1][0]: # 정렬한 배열 중 최댓값과 동일한 것이 여러 개 있으면 다 골라준다.
break
index = max_money[-i][1] # 확인할 라인
for j in range(n):
for k in range(j + m, n, m): # 최댓값이 나오면 바꿔준다.
max_result = max(max_result, moneys[index][j] + moneys[index][k])
print(f'#{tc} {max_result}')
🔍 결과
Author And Source
이 문제에 관하여([SWEA] 2115. [모의 SW 역량테스트] 벌꿀채취), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yunhlim/SWEA-2115.-모의-SW-역량테스트-벌꿀채취저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)