휴가(삼성 SW역량평가 기출문제)

카운셀러로 일하고 있는 현수는 오늘부터 N+1일째 되는 날 휴가를 가기 위해서,

남은 N일 동안 최대한 많은 상담을 해서 휴가비를 넉넉히 만들어 휴가를 떠나려 한다.

현수가 다니는 회사에 하루에 하나씩 서로 다른 사람의 상담이 예약되어 있다.

각각의 상담은 상담을 완료하는데 걸리는 날 수 T와 상담을 했을 때 받을 수 있는 금액 P로 이루어져 있다.

 

만약 N = 7이고, 아래와 같이 예약이 잡혔다면

1일에 잡혀있는 상담은 총 4일이 걸리며, 상담했을 때 받을 수 있는 금액은 20이다.

만약 1일에 예약된 상담을 하면 4일까지는 상담을 할 수가 없다.

하나의 상담이 하루를 넘어가는 경우가 많기 때문에 현수는 예약된 모든 상담을 혼자 할 수 없어 최대 이익이 나는 상담 스케쥴을 짜기로 했다.

휴가를 떠나기 전에 할 수 있는 상담의 최대 이익은 1일, 5일, 7일에 있는 상담을 하는 것이 며, 이때의 이익은 20+30+10=60이다. 현수가 휴가를 가기 위해 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

 

▣ 입력설명

첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.

둘째 줄부터 1일부터 N일까지 순서대로 주어진다. (1 ≤ T ≤ 7, 1 ≤ P ≤ 100)

 

▣ 출력설명 첫째 줄에 현수가 얻을 수 있는 최대 이익을 출력한다.

 

▣ 입력예제

7

4 20

2 10

3 15

3 20

2 30

2 20

1 10

 

▣ 출력예제 

60

---

내가 쓴 코드

import sys
sys.stdin = open("input.txt",'rt')
input = sys.stdin.readline
def DFS(v, total_earning):
    global max_earning
    if v == N:
        if total_earning > max_earning:
            max_earning = total_earning
    else:
        if v+days[v] <= N:
            DFS(v + days[v], total_earning + earnings[v])
        DFS(v+1, total_earning)

if __name__=="__main__":
    N = int(input())
    days = []
    earnings = []
    for _ in range(N):
        a,b = map(int, input().split())
        days.append(a)
        earnings.append(b)
    max_earning = 0
    DFS(0,0)
    print(max_earning)

 

모범답안

#모범답안
import sys
sys.stdin = open("input.txt",'rt')
def DFS(L, sum):
    global res
    if L == n+1:
        if sum > res:
            res = sum
    else:
        if L + T[L] <= n+1:
            DFS(L+T[L], sum+P[L])
        DFS(L+1, sum)

if __name__=="__main__":
    n = int(input())
    T = list()
    P = list()
    for i in range(n):
        a, b = map(int, input().split())
        T.append(a)
        P.append(b)
    res = -2147000000
    T.insert(0,0)
    P.insert(0,0)
    DFS(1,0)
    print(res)

 

느낀점

1. 상태트리의 가지 수는 두개, 상담한다 안한다로 나눈다.
날짜가 N이 되면 최댓값 비교하고 리턴
그 전에는 DFS를 반복하되, 상담하는 경우는 소요일을 더했을 때 N보다 작거나 같은 경우에만
DFS(현재인덱스+소요일)로 진행한다.
소요일을 더했을때 N보다 크다면 그건 그냥 상담안한다로 넘어가게끔 DFS(현재인덱스+1)

2. 와 모범답안이랑 완전히 똑같이 풀었다 머지. ? 너무 잘했다 우니여...
완전뿌듯해서 당장 다시 풀어봐야겠다 우하핫

3. DFS는 크게 두 가지 종류가 있는 것 같다.
부분집합의 개념으로 가지를 단 두 개(포함한다 안한다)로 푸는 문제와,
경로의 개념으로 가지를 여러 개(반복문으로 제어)로 푸는 문제.
이 문제는 부분집합의 개념이었던 것!

4. 문제에서는 보통 1일, 이런식으로 1부터 시작하는데 리스트를 사용하는 경우
인덱스를 사용하면 0부터 시작하니까 모범답안은 자주 0을 사용안하고 1부터 쓰게
안쓰는 0을 추가하는데.. 난 사용하는 숫자를 -1해서 인덱스의 개념에 맞추는 경향이 있다.
물론 0을 추가해서 숫자 그대로 사용하는게 더 편할듯도 한데,
지금까지 계속 인덱스의 개념에 맞춰서 사용했다보니 더 헷갈린다.
고쳐봐야겠당!

---

다시 풀어보기

#다시
import sys
sys.stdin = open("input.txt",'rt')
input = sys.stdin.readline

def DFS(v, total_earning):
    global max_earning
    if v == N+1:
        if total_earning > max_earning:
            max_earning = total_earning
    else:
        if v+days[v] <= N+1:
            DFS(v+days[v], total_earning+earnings[v])
        DFS(v+1, total_earning)

if __name__=="__main__":
    N = int(input())
    days = list()
    earnings = list()
    for _ in range(N):
        a,b = map(int, input().split())
        days.append(a)
        earnings.append(b)
    max_earning = -2147000000
    days.insert(0,0)
    earnings.insert(0,0)
    DFS(1,0)
    print(max_earning)