[코테준비] 1. 백준- 퇴사(14501) python "삼성 SW 역량 테스트 기출 문제"

현재 삼성 코딩테스트를 위해서 4인 코테 스터디를 운영하고 있다. 다 함께 삼성 들어가길🍀🍀 백준에 있는 [삼성 SW 역량 테스트 기출 문제]를 매일 2문제씩 풀 계획이다. 풀고나서, 문제에 대한 답안을 업데이트 할 예정! 푸는 방법이 다양하다면, 각 방법에 대한 설명 또한 작성예정이다. 

각 문제당 - 링크, 난이도, 분류, 직접 푼 여부, 풀이, 참고할만한 자료링크

문제를 푸는 순서는 난이도가 낮은 순으로! (브론즈 문제도 있었는데, 놓쳐서 실버 먼저 풀게 되었다)

• 백준 "삼성 기출문제 문제집": https://www.acmicpc.net/workbook/view/1152

문제집: 삼성 SW 역량 테스트 기출 문제 (baekjoon)

• About 삼성 코테
  • 매우 많이 떨어진다고 한다.  꼭 열심히 준비하자
  • 파이참사용
  • 오프라인
  • 2문제 
  • 백준 골드 2정도? (확실 X)
  • 구현 많음
  • itertools 사용 못함 ㅜㅜ

---

1. 퇴사

• 링크:https://www.acmicpc.net/problem/14501
• 난이도:실버3
• 분류: 브루트포스, DP
• 직접 푼 여부: X
• 언어: 파이썬

• 참고영상: https://www.youtube.com/watch?v=9GLuPXiIC3s 

 

1) 풀이 1 - 브루트포스

#하나하나 다 보기 (2**N = 2**15 < (10**3)**2 r가능!)
import sys
#sys. setrecursionlimit(10000)
# input
n = int(sys.stdin.readline())
sch = [list(map(int,sys.stdin.readline().split())) for _ in range(n)]

# back tracking
def dfs(nn, tempans):
    # nn: 며칠인지
    # tempans: temp ans
    global ans #def 밖에 있는 것과 연동
    if nn >= n:
        ans=max(tempans, ans) # 다른 길로 갔을 때의 값과 비교해서 큰 것
        return
    # 상담 실행 o - 퇴사전까지만 가능
    if nn+sch[nn][0]<=n:
        dfs(nn+sch[nn][0], tempans+sch[nn][1])
    # 상담 실행 X
    dfs(nn+1, tempans)
    
ans= 0
dfs(0,0)

print(ans)

 

2. 풀이 2 - DP

* 관련 내용을 이해하면 업데이트 예정 이해완

* dp이해하기에 좋은 유튜브다! C언어이긴한데 앞에 개념부분만 봐도 굳!!: https://www.youtube.com/watch?v=VEbh7lCu7Ic 

# DP -추천 유튜브: https://www.youtube.com/watch?v=VEbh7lCu7Ic
import sys

# 1. input 받기 ---------
n = int(sys.stdin.readline())
t=[]
p=[]
for i in range(n):
    tt, pp =map(int,sys.stdin.readline().split())
    t.append(tt)
    p.append(pp)
  
# 2. dp 준비 ---------
dp = [0]*(n+1)
# 점화식: dp(i) = max(dp(i+1), dp(i+t[i])+p[i]) -> 재귀말고 dp table 이용
# 애초에 dp[n] =0 이므로, 0으로 값 다시 넣을 필요 없음

# 3. dp table채우기
for i in range(n-1, -1,-1): 
    # n, n-1 ... 0
    if i+t[i] <= (n):
        # 3-1) 일을 할 수 있으면 (퇴사전에 일이 끝나면), 일을 하는 것과 안하는 것 비교
        dp[i] = max(dp[i+t[i]] + p[i], dp[i+1]) # 하는 것, 안하는 것
    else:
        # 3-2) 일을 할 수 없으면 - 안하는 것 밖에 안됨
        dp[i] = dp[i+1]
print(dp[0])

 

---