본문 바로가기

분류 전체보기

(402)
[백준 8987번] 전봇대 (Python3) def cal(x): if not memo.get(x): memo[x] = sum([abs(i*x-data[i]) for i in range(N)]) return memo[x] N = int(input()) data = [*map(int,input().split())] memo = {} last = memo[0] = sum(data) x,c = 1,0 while c >= 0: if cal(x) < last and cal(x) < cal(x-1): last = cal(x) x += 2**c c += 1 else: last = cal(x-2**c) x -= 2**(c-1) c -= 2 print(min(memo.values())) 구현은 간단하지만 아이디어를 떠올리기 굉장히 어려웠다. 기본적으로 이분탐색을 ..
[백준 18186번] 라면 사기 (Large) N,B,C = map(int,input().split()) A = [*map(int,input().split())] if B A[i] and A[i+1]>A[i+2]: MIN = min(A[i],A[i+1]-A[i+2]) cost += MIN*(B+C) A[i] -= MIN A[i+1] -= MIN continue MIN = min(A[i],A[i+1],A[i+2]) cost += MIN*(B+C*2) A[i] -= MIN A[i+1] -= MIN A[i+2] -= MIN print(cost) 라면 사기 small [백준 18185번] 라면 사기 (Small) (tistory.com) 의 확장버전이다. 라면 사기 small과 풀이 자체는 완전히 똑같다. 3,5,7을 B,B+C,B+2C로 나타냈을 뿐이다...
[백준 18185번] 라면 사기 (Small) N = int(input()) A = [*map(int,input().split())] cost = i = 0 while i A[i] and A[i+1]>A[i+2]: MIN = min(A[i],A[i+1]-A[i+2]) cost += MIN*5 A[i] -= MIN A[i+1] -= MIN continue MIN = min(A[i],A[i+1],A[..
[백준 1948번] 임계경로 (Python3) import sys input = sys.stdin.readline from collections import deque sys.setrecursionlimit(10**6) def countpath(now): global cnt if visited[now]: return visited[now] = 1 for last in path[now]: cnt += 1 countpath(last) N,M = int(input()),int(input()) graph = [[] for i in range(N+1)] indegree = [0]*(N+1) for _ in range(M): x,y,w = map(int,input().split()) graph[x].append((y,w)) indegree[y] += 1 sta..
[백준 1214번] 쿨한 물건 구매 (Python3) D,P,Q = map(int,input().split()) P,Q = max(P,Q),min(P,Q) MIN = 1e10 for i in range(min(D//P,Q)+1): MIN = min(MIN,(Q-(D-P*i)%Q)%Q) MIN = min(MIN,(P-(D%P))%P) print(D+MIN) 재미있는 문제였다. 코드를 보면 알다싶이 매우 간단하게 구현 가능하지만, 아이디어를 떠올리는데 약간의 고민이 필요했다. 알고리즘을 설명하면, 1. 더 큰 수를 P, 더 작은 수를 Q로 둔다. 2. P를 한개도 안낼 때의 금액부터, 한개 낼때, 두개 낼때... 를 for문으로 돌려 지불 가격의 최솟값을 구한다. 3. 이때 for문은 D//P와 Q 중 더 작은 값까지 돌린다. (Q까지 돌리는 이유는 P를 Q번..
[백준 1422번] 숫자의 신 (Python3) K,N = map(int,input().split()) nums = [] for _ in range(K): n = input() x = n*(18//len(n)) for i in range(18%len(n)): x += n[i] nums.append((len(n),x,n)) nums.sort(reverse=True) for _ in range(N-K): nums.append(nums[0]) nums1 = [] for i in range(N): l,x,n = nums[i] nums1.append((x,n)) nums1.sort(reverse=True) for i in range(N): print(nums1[i][1],end="") 큰 수 만들기 [백준 16496번] 큰 수 만들기 (Python3) (tis..
[백준 11440번] 피보나치 수의 제곱의 합 (Python3) mod = 1000000007 def cal(A,n): if n==1: return A cal2 = cal(A,n//2) if n%2: return multiply(multiply(cal2,cal2),A) return multiply(cal2,cal2) def multiply(A,B): result = [[0]*3 for i in range(3)] for i in range(3): for j in range(3): for k in range(3): result[i][j] += A[i][k]*B[k][j]%mod result[i][j] %=mod return result N = int(input()) if N == 1: print(1) else: matrix = [[2,2,-1],[1,0,0],[0,1,0..
[백준 15678번] 연세워터파크 (Python3) import sys,heapq input = sys.stdin.readline N,D = map(int,input().split()) step = [*map(int,input().split())] DP = [0]*N hq = [] for i in range(N-1,-1,-1): DP[i] += step[i] while hq and hq[0][1] > i+D: heapq.heappop(hq) if hq: DP[i] -= hq[0][0] if DP[i] > 0: heapq.heappush(hq,(-DP[i],i)) print(max(DP)) 최솟값 찾기 11003번: 최솟값 찾기 (acmicpc.net) 문제와 거의 똑같은 방식으로 해결하였다. 일단 이 문제에서 징검다리를 한쪽 방향으로만 건너야 한다는 말은..