For Programmer

이 문제의 핵심은 여러 경로들을 지나간 횟수와 그 때 현재의 노드를 기준으로 dp[현재의 노드][지나간 횟수]를 저장하는 것이다. 3을 기준으로 본다면 1 -> 2 -> 3 -> 4 ... 2 -> 1 -> 4 -> 3 -> 5 ... 4 -> 2 -> 3 -> 6.... 과 같이 3이 3번째인 수많은 경로가 나온다고 할 때 3번째에 3의 정점을 지나가는 경우의 수는 미리 구해놓으면 다음번에 지나갈 때 굳이 또 검사를 안해도 된다는 것이다. 또한 10^9 + 7을 계산할 때마다 나누어서 저장해주어야 한다는 점 또한 잘 체크해야 한다. import sys def dfs(cur, cnt): if cnt > 7: return 1 if dp[cur][cnt] != -1: return dp[cur][cnt] dp..

사실 dp문제들 보면 바텀업으로 접근하기 위해 점화식 찾기가 여간 쉬운일이 아니다. 그래서 무조건적으로 탑다운으로 재귀로 짤려고 노력을 많이한다. 다음 코드도 재귀코드이며 잘 분석해보길 바란다. import sys sys.setrecursionlimit(50000) N = int(input()) homes = [[0, 0, 0]] + [list(map(int, input().split())) for _ in range(N)] dp = [[1 한 재귀안에서 한번에 돌아서 계산하기 위해 homes의 첫번째 행에 [0,0,0] 을 추가했다.

이런 문제는 그냥 탑다운으로 풀어버리는 습관을 가져버렸다. C++이면 무조건 통과인데 N이 조금더 커지면 파이썬은 재귀제한을 풀어도 재귀 스택 용량 초과로 불가능하다... 하지만 이러한 재귀 식을 한번 이해해버리면 아주 풀기가 쉽기 때문에 탑다운 방식을 애용하자. (평균적인 재귀와는 달리 끝까지 재귀를 타고 들어가서 한개씩 쌓아서 나오는 구조이다.) def dfs(depth, weight): global ans if weight > K: return -100000000 if depth == N: return 0 if dp[depth][weight] != -1: return dp[depth][weight] dp[depth][weight] = max(dfs(depth + 1, weight + bag[dept..

1. Top down 방식 import sys sys.setrecursionlimit(100000) N = int(input()) A = list(map(int, input().split())) + [0] dp = [[-1 for _ in range(N + 1)] for _ in range(N + 1)] def dfs(cur, pre): if cur == N: return 0 if dp[cur][pre] != - 1: return dp[cur][pre] if A[cur] > A[pre]: ret = max(dfs(cur + 1, cur) + 1, dfs(cur + 1, pre)) else: ret = dfs(cur + 1, pre) dp[cur][pre] = ret return dp[cur][pre] p..

파이썬도 N 제한이 엄청 크지 않다면 Top-down 으로 메모제이션 적용시켜 재귀로 dp를 해결할 수 있다. 1. Top down 방식 import sys input = sys.stdin.readline N = int(input()) stair = [int(input()) for _ in range(N)] + [0] dp = [[-1] * 3 for _ in range(N)] # 계단을 1개 밟고 올때와 2개 밟고 올때 나눠서 DP def dfs(cur, cnt): if cnt > 2: return -100000000 if cur > N - 1: return -100000000 elif cur == N - 1: return 0 if cur != -1 and dp[cur][cnt] != -1: retur..

이 문제의 접근 방식은 https://ji-gwang.tistory.com/431 해당 문제와 굉장히 유사하다. 해당문제의 풀이를 보고 오자. 이 문제를 풀기 위해서 3가지의 과정을 떠올려야 한다. 1. 누적합(어떤 수 N 보다 작은 수는 몇개 있는지) 즉, (N개까지의 누적합) - (N - 1 개 까지의 누적합)은 N일 때 개수와 같다. 2. 이분탐색 ( 찾고하는 수 N을 계속 이분탐색하며 N의 개수가 홀수이면 계속해서 숫자를 낮춰가며 찾아나간다. 단, 짝수이면 숫자를 올려 찾는다. 이렇게 개수가 홀수인 제일 왼쪽지점(즉, 제일 작은값)의 값을 찾아야한다.) 3. 딕셔너리에 찾은 값들을 저장해놓고 개수를 구한다. ans가 정답이라면 dp[ans] - dp[ans - 1] 로 구할 수 있다. 단, dp[..

접근 방식을 몰라서 결국 정답을 봤다. 문제의 접근방식은 다음과 같다. # N이 100일 때 # 1 2 3 1단 # 2 4 6 2단 # 3 6 9 3단 # ... # 100 200 300 10000 N단 과 같이 존재한다. 만약 여기서 오름차순 후 7보다 작은수가 몇개 있냐 라고한다면 # 7보다 작은 수가 몇개 있냐 # 1 2 3 4 5 6 7 8 9 # 1 3 5 6 6 8 8 8 9 ... # x x x x x o o o o ... 해당 수의 가장작은 숫자 찾기 위와같이 자기보다 작은수를 저장한다고 치자. 그러면 1은 1개 2는 1의개수 + 2의개수 3은 1의개수+ 2의개수 +3의개수 가 된다. 즉, 다음과 같이 구할수 있으며 이러한 공식을 그대로 이용한다면 다음과 같이 구할 수 있다. # 100 *..

이 문제 이분탐색의 시작값을 1로설정했다가 하루종일 해맸다. 시작값도 중요하다는것을 알았으며 시작값과 끝값을 잘설정해주어야하는 문제도 있다!! 자세한 설명은 주석으로 달아놨으며 간단히 구슬의 개수를 이분탐색돌면서 그리디와 같이 앞에서부터 해당 구슬의 개수만큼 묶어주면 된다. 그러나 만약 만들어야 하는 팀의 개수와 남은 인원이 동일하다면 한명씩 그냥 한팀으로 만들어주면 되는 체크만 잘하면 쉽게 해결할 수 있다. (물론 이걸 간단히 코드화하는데는 2시간이 걸렸다..) N, M = map(int, input().split()) array = list(map(int, input().split())) s = max(array) # 시작값을 최대값으로 설정(중요!!) e = sum(array) # 끝값을 전체합으로..