For Programmer

간단한 이분탐색 문제이다. 랜선의 크기를 절반씩 줄여나가면서 검사하면 된다. (K의 무수하게 크다면 우선 생각을 해봐야 하는 것이 이분탐색이다. 또한 N도 10000이기에 N^2으로 돌수가 없다. ) import sys input = sys.stdin.readline K, N = map(int, input().split()) len = [] for _ in range(K): len.append(int(input())) s = 1 e = max(len) def check(mid): total = 0 for i in len: total += (i // mid) return total >= N ans = 0 while s

간단한 이진탐색 문제입니다. 자를 높이를 반씩 줄여나가면서 탐색하면 쉽게 구할 수 있습니다. 단, 검사할 때 max메서드 쓰면 python3에서 시간초과 납니다. 따라서 pypy3에서 max사용 가능하고 그이외의 경우 if로 비교하셔야 됩니다. import sys input = sys.stdin.readline N, M = map(int, input().split()) trees = list(map(int, input().split())) s = 0 e = max(trees) ans = 0 def check(mid): total = 0 for i in trees: total += max(0, i - mid) #if i - mid > 0 total += i - mid 로 변경(파이썬3로 제출시) retur..

이분탐색 문제는 대부분 출력에서 나오는 값을 이분탐색하며 찾는 방식이 많다. 이문제 또한 그러한 방식이다. 이분탐색할 질투심 x를 1~10^9 까지 범위로 잡아주고 반씩 줄여나가면서 해당 질투심일 때 필요한 사람수를 비교하여 구해진 사람수가 필요한 사람수 보다 많으면 사람수를 줄이기 위해 질투심을 높여야 하기 때문에 탐색 시작인덱스를 증가시켜주고 만약 적으면 질투심을 낮추어야 하기때문에 끝인덱스를 줄여주는 식으로 탐색하면 된다. import sys input = sys.stdin.readline N, M = map(int, input().split()) array = [] for _ in range(M): array.append(int(input())) s = 1 # 1명부터 e = 10 ** 9 # 1..

파이썬 딕셔너리 사용하면 쉽게해결 할 수 있으나 정렬 후 이분탐색으로 찾을려는 수 x의 양끝 인덱스를 찾아서 그 2개를 빼주고 1을 더하는 식으로 개수를 구했다. (python3로 제출하면 시간초과가 발생하고 pypy로 제출해야 시간초과발생하지 않습니다.) N = int(input()) card = list(map(int, input().split())) M = int(input()) saguen = list(map(int, input().split())) card.sort() for i in range(M): s = 0 e = N - 1 ans_1 = 0 # 시작부분 찾기 while s saguen[i]: e = mid - 1 else: s = mid + 1 s = 0 e = N - 1 ans_2 = ..

파이썬의 딕셔너리를 사용하면 쉽게 해결할 수 있으나 해당 문제를 이분탐색으로 구현해 보았다. N = int(input()) card = list(map(int, input().split())) M = int(input()) saguen = list(map(int, input().split())) card.sort() for i in range(M): s = 0 e = N - 1 x = saguen[i] ans = 0 while s

사실 누적합이 주어진 숫자의 범위가 아주 크기 때문에 해결하기 위해선 정확한 점화식을 찾아야 한다. 그렇지 않을 경우 TLE에 걸리기 때문에 조금 어렵다. 상향식 DP와 비슷한 개념이기 떄문에 아무리 생각해도 모르겠어서 해당 문제에 대해서 https://hongcoding.tistory.com/6 해당 글에서 힌트를 얻어 풀었다. 자세한 설명은 주석으로 달아 놨다. import sys input = sys.stdin.readline N, H = map(int, input().split()) down = [0] * (H + 1) up = [0] * (H + 1) for i in range(N): if i % 2 == 0: down[int(input())] += 1 # 입력받은 길이의 개수를 저장 else:..

해당문제는 누적합의 응용 문제라고 생각하면 된다. 우선 누적합을 구해놓고 누적합을 처음부터 N 까지 돌면서 해당 값의 찾고하는 값 K 를 뺀 cnt리스트의 인덱스에 저장되어 있는 값을 우선 더해준다.(즉, cnt[prefix[i] - K]) 그 후 해당 누적합의 개수를 cnt 리스트의 해당 인덱스에 +1개 추가해준다. (즉, cnt[prefix[i]] += 1) 하지만 K의 값이 아주크거나 음수가 존재할 경우 cnt의 배열크기가 아주 커지게 된다. 혹은 음수 계산을 할 수가 없다. 따라서 딕셔너리 형태로 변환하여 위의 상황을 진행해야 한다. N, K = map(int, input().split()) arr = [0] + list(map(int, input().split())) # 입력받은 수들을 저장 p..

해당 문제 dp적용할 점화식을 생각하기가 생각보다 까다로웠다. 해당 문제의 점화식은 다음과 같다. 어떠한 점 i, j 가 있으면 해당 지점까지 1~9 까지 개수를 3차원 dp에 dp[i][j][k] += 1로 (k는 해당 array[i][j] 의 값) 개수를 저장을 해놓는다. 그 후 개수를 누적해주기 위해 그 윗줄의 같은 행 즉 dp[i - 1][j] + 그 전열의 같은행 dp[i][j -1] 그리고 2번더해진 해당부분 dp[i -1][j -1]을 한번 빼주면 된다. 그 후 이렇게 저장된 dp의 값을 이용해 입력받은 4개의 점을 기준으로 1~10 까지 반복문을 돌면서 dp[x2][y2][k] - dp[x2][y1 - 1][k] - dp[x1-1][y2][k] + dp[x1-1][y1-1][k] 와 같은 ..