2327번 말아톤

문제 설명

이번 문제는 사람들의 키의 합이 H가 되도록하는 팀 중에서 가장 느린 사람이 가장 빠르게 되도록 팀을 선발하는 방법을 찾는 문제입니다.

팀의 학생들의 키 총합이 H만 된다면 구성원이 몇 명이든 상관 없습니다.

각 i번째 학생의 정보는 hi, si가 주어집니다.(hi = i 번째 학생의 키, si = i 번째 학생의 속도)

 

문제 풀이

아이디어

dynamic programming

현재 내가 살펴보고 있는 선수 i가 팀의 구성원이 될 경우를 살펴보도록 하겠습니다.

이 선수가 속한 팀의 다른 구성원들의 키의 합은 H-hi가 될 것입니다.

만약, 지금까지 살펴본 선수들로 구성할 수 있는 팀의 키의 총합이 될 수 있는 경우를 저장하고 있었다면, 키의 합이 H-hi이 되는 팀이 있는지 확인해보면 됩니다.

그렇다면 현재까지 필요한 정보는

• 현재까지 살펴본 선수들로 구성할 수 있는 팀의 키의 합이 될 수 있는 경우를 저장하고 있어야 합니다.

위에 해당하는 풀이 방법으로는 dp를 떠올릴 수 있습니다.

 

정렬

우리가 찾는 것은 키의 합이 H가 되는 팀의 구성원 중 가장 느린 사람이 가장 빠르게 되는 팀의 그 느린 사람을 찾는 것입니다.

만약 현재까지 살펴본 사람들이 무조건 자신보다 빠르거나 속도가 같은 사람이고, 아직 살펴보지 않은 사람들은 자신보다 무조건 느리거나 속도가 같은 사람이라고 해보도록 하겠습니다.

그렇다면, 현재까지 dp로 저장된 키의 합 정보에서 H-hi를 키의 합으로 갖는 팀이 있다면, 그 팀에서는 현재 살펴보고 있는 i가 가장 느린 사람이고 키의 합이 H가 되는 팀 중에서 가장 느린 사람 중 i가 가장 빠른 사람이 됩니다.

그렇다면 여기서 알게 된 정보는

• 선수들을 살펴보는 순서는 달리기가 빠른 사람부터 느린 사람 순으로 살펴보도록 합니다.

 

풀이

정렬

dp를 이용한 풀이를 하기 전에, 우선 N명의 사람들을 달리기가 빠른 순으로 정렬해 줍니다.

이 방법은 각자 다르겠지만, 필자와 같은 경우 모든 정보를 [hi, si] 형식으로 info 변수에 저장하고 있기 때문에 python의 custom sort 방식을 이용했습니다.

from functools import cmp_to_key

def compare(x,y):
    if x[1]!=y[1]:
        return y[1]-x[1]
    else:
        return y[0]-x[0]
        
info.sort(key=cmp_to_key(compare))

info의 원소들을 si가 높은 순으로 정렬하고, si가 같다면 hi가 높은 순으로 정렬해줍니다.

 

dp 풀이 1

우선 N*H 배열에 정보를 저장하는 경우를 살펴보도록 하겠습니다.

달리기 순으로 정렬된 배열에서 dp[i][j]는 i번째 사람까지의 부분 집합 중에서 키의 합이 j가 되는지 True, False 값을 저장해줍니다.

그렇다면 dp[i][j] = dp[i-1][j] or dp[i-1][j-h[i]] 로 정의할 수 있습니다.

 

위의 N*H를 이용해 풀어본 코드(메모리 초과) http://boj.kr/caf8a8e3094c45eb944876a34e0531bd

공유 소스 보기

 

dp 풀이 2

위의 식 dp[i][j] = dp[i-1][j] or dp[i-1][j-h[i]]를 살펴 보도록 하겠습니다.

dp[i]는 dp[i-1]만을 이용해 만들어지는 것을 볼 수 있습니다.

그렇다는 것은 N*H 크기의 배열이 아닌 H크기의 배열인 dp[i-1]만 가지고 있어도, dp[i]를 만들 수 있다는 것입니다.

즉, dp의 크기는 H로 충분하고, 이전 dp의 내용만 가지고 원하는 값을 찾을 수 있다는 것입니다.

 

2번째 풀이의 코드를 보고 싶다면 아래 GitHub 코드 링크로 살펴보면 될 것 같습니다.

 

 

해결

H-hi를 만족하는 부분 집합이 있는지, 그 부분 집합을 찾았을 때 어떤 순서로 찾았을 경우 답을 찾을 수 있는지 생각해야되는 문제여서 이번 문제는 힌트를 보고 풀게 되었습니다.....

dp에 대한 풀이를 다시 복습할 수 있어 좋았고, 상황에 맞게 dp를 사용할 수 있도록 반복해야 될 것 같습니다.

 

문제 링크 : https://www.acmicpc.net/problem/2327

2327번: 말아톤

코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/2327.py