[백준 #14501, Python] 퇴사

>> 오늘의 TMI 코드가 필요하신 분들이라면 스킵 부탁~!<<

진짜 한 달?넘게 손대보는 알고리즘 문제 + 코딩이란 것 자체 ㅋㅋㅋㅋㅋㅋ실력이 싸피 입소때로 회춘한듯 하당^^,,

사실 그동안 안한건 나태 지분이 80% 정도 있었지만, 결국 최종면접에서 떨어졌다는게 가장 컸다 ㅎ^ㅎ,,,

주변에 하도 찡찡대서 넘모 많이 들었을테지만 너무 타격이 컸다 진짜루 ㅋㅋㅋㅋ 해외 근무에 1차면접도 나름,,? 무난하게 본 것 같았구, 대규모 채용에 이거 안되면 진짜 웃긴다~ 그리구 최종 배수도 작을거라구 생각해서 진짜 나 쌒희 떠나는 시나리오도 다써놓앗구 자취방에 물품들도 일부러 안사놓았는데 그래서 그런가^^,,, 꾸역꾸역 뭔가를 하긴하지만 일주일 내내 폰만 보구 원래 군것질 잘 안했는데 식욕도 엄청 늘었다 다이어트 급해 8282 ㅋㅅㅋ,, 암튼 주변에 친구들 이번에 다 취업하고, 취업을 위해서는 공부를 끝까지 하는 쌒희 사람들과 주변 취업을 향해 질주하는 내친구들 사이에서 갈등이 정말 크당,, 데이터 분석 경험을 배터리에서 어떻게 활용할거라는 질문에 대답두 못하고 하아~~~~~~ 어렵당

아무튼 그런 심정으로 이름이 맘에 들어서 고른 문제. 쨋든 지금 남은 쌒희나 열심히 하자!~!~! 팀도 좋고 개발 주제도 재밌어보인다, PJT 2에 빅데이터까지 해보면 좀 큰 도움이 되지 않을깟,? 아무튼 나에게 강제로 알고리즘 문제를 풀게해주는 사람들이 있어서 참 다행이다 좋은곳이야 쌒희는

 

[ 문제 ]

상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.

오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.

백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.

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

N = 7인 경우에 다음과 같은 상담 일정표를 보자.

 1일2일3일4일5일6일7일TiPi

3	5	1	1	2	4	2
10	20	10	20	15	40	200

1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.

상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.

또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.

퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.

상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

 

[풀이]

첨에 거의 다 맞고 90% 쯤에서 계속 미통과되서 진짜 뭐지? 하고 게시판 예시도 다 돌려봤는데, 다 통과하는 것 같아서 고민했는데 ㅋㅋㅋ답이 없을때 0으로 출력이 안되서 틀렸던 거다. 참눼

이 문제는 좀 뿌듯했는데 진짜 오랜만에 해서 SYS도 기억안나고 했는데, 엄청 쉬운 DP?를 내 손으로 직접 적용시켜본 문제라 넘 뿌듯했다. i 번째 날을 선택하면, 그 상담이 끝난 다음날 부터 선택이 가능한 애들(퇴사날을 넘기지 않는 애들)에 대한 총액을 모두 D에 저장하고, 계속 반복! 하면 문제가 쓩 풀린다

 

from sys import stdin
N = int(stdin.readline())
arr = [list(map(int,stdin.readline().split())) for _ in range(N)]
D = [0]*N
for i in range(N):
    if (i+arr[i][0] -1 <N): #이 상담을 채택했을때 기간이 퇴사 전인지
        if D[i] < arr[i][1]:
            D[i] = arr[i][1]
    else:
        continue
    for j in range(i+1,N):
        if j - i > arr[i][0] -1 :
            if j + arr[j][0] -1 < N:
                if D[j] < D[i] + arr[j][1]:
                    D[j] =  D[i] + arr[j][1]
        else:
            continue
print(max(D))