For Programmer

이런 문제는 그냥 탑다운으로 풀어버리는 습관을 가져버렸다. 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) # 끝값을 전체합으로..

해당 문제 이분탐색이라는 힌트를 못봤으면 한참 걸렸을 꺼 같다. 이분탐색이라고 생각하고 접근하면 생각보다 어렵지않다. 1. 우선 거리를 이분탐색으로 계속 검색해준다. 그리고 그 거리를 기준으로 입력받은 집 배열을 투포인터로 돈다. 처음 투포인터는 s 는 첫번째 집을 e는 두번째 집을 가리키도록 한다. 2. 만약에 s가 가리키는 집과 e가 가리키는 집의 거리가 현재 이분탐색하는 거리와 동일하거나 크다면 설치 가능한 집의 개수를 한개 추가해준다. 그 후 s를 e가 가리키는 집으로 그리고 e는 원래 e가 가리키는 집의 그다음 집으로 이동해준다. 3. 그러나 만약 설치할 수 없다면(즉, 두집 사이의 거리가 설치하려는 거리보다 더 가깝다면) s는 냅두고 e만 그 다음집으로 이동하면서 계속 검사해준다. 자세한 설명..

well-known 이분탐색문제이다. 그냥 전체 범위에서 반씩 줄여나가면서 검사하면 된다. import sys input = sys.stdin.readline N, K = map(int, input().split()) mak = [int(input()) for _ in range(N)] s = 1 e = max(mak) def check(mid): total = 0 for i in mak: total += (i // mid) return K