맛대의 블로그

https://www.acmicpc.net/problem/28103 로직 사람을 한명씩 가진돈과 비교하여 계산할 경우 N이 너무 커서 시간초과가 발생 가격의 경우 10**6으로 반복문을 돌려도 문제가 발생하지 않는 범위 일단 모두 제일 싼 값으로 구매한 후 남은 돈으로 계산 시작 (X -= default*N) 위 방법으로 계산하기 위해 물건의 가격을 제일 값싼 물건과의 가격차이로 변경 가장 비싼물건부터 여유있는 돈의 수만큼 구매, 이 때 현재 남아있는 사람 수(N)와 비교하여 낮은 값으로 계산 현재 가진돈이 물건 값 대비 매우 많을 경우 X//price 계산시 사람 수보다 많은 물건을 사게됨 가장 값싼 물건과의 가격차이로 list를 변경하여 prices[-1]은 0이 되어 X//price 시 zerodi..

https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 설명 로직 설명 1. 현재 지어도 상관 없는 건물들을 짓는다. 2. 해당 건물이 완성됨에 따라 선행조건이 해결되는 것을 기록한다. 3. 모든 건물이 지어질 때 까지 1번과 2번을 반복한다 변수 설명 spending_time : 해당 건물을 건설시 필요한 시간을 기록 build_time : 해당 건물을 건설하기 위해 총 걸리는 시간 기록(3번 건물을 짓기 위해 1번 건물이 필요시 시간 )..

https://www.acmicpc.net/problem/2887 MST(최소 신장 트리)문제 전체적인 로직 x 좌표, y좌표, z좌표를 따로 저장(행성 번호와 함께 저장) KRUSKAL 알고리즘 이용 x,y,z 좌표를 정렬한 뒤, 앞 뒤 행성간의 거리 측정해서 저장(먼 거리의 행성은 끼리 계산할 필요 x) 측정된 거리 순서로 정렬 정렬 순서로 연결 코드 설명 union 함수 a행성과 b행성을 연결하는 함수 depth : 행성 연결이 지름이 길게 연결되지 않고 균등하게 붙어지게 하기 위한 최적화 find_root 함수 n번 행성(node)가 어디로 연결되어 있는지 확인하는 함수 group[n] = find_root(T) 은 find_root를 자주 사용할 경우 함수 호출을 줄이기 위해 최적화 find_m..

https://www.acmicpc.net/problem/1939 2개의 풀이방법 다익스트라(dijkstra) 두 지점중 한 지점(start)에서 다익스트라를 이용하여 다른 지점(end)지점의 최대 무게를 구하는 방식 새로운 길이 기존의 최대 중량 길(ls[node])보다 괜찮을 경우 탐색을 이어가는 방식 python의 heapq의 경우 작은값을 우선순위로 진행하기에 음수값을 저장하여 큰 값을 우선순위로 사용 중량이 큰 다리(길?,루트?) 부터 탐색하는 방식 import heapq,sys input = sys.stdin.readline def dijkstra(node:int,N:int,end:int)->int: INF = 1000000001 h = [(-INF,node)] ls = [0]*(N+1) ls..

https://www.acmicpc.net/problem/11505 세그먼트 트리 활용 트리 구조 0번 노드는 비워둠 1번 노드는 2,3 번 노드의 곱, 2번 노드는 4,5번 노드의 곱 (이진 트리 형식) 업데이트 1번 노드는 모든 숫자의 곱 1번 노드부터 밑으로 해당 index를 가진 노드로 이동하며 업데이트(재귀 형태로 코드가 짜여 있어서 제일 밑 노드부터 업데이트 됨) index가 1~7까지 존재 할 때, 3번 노드(타겟)를 업데이트, 1~7의 중간값은 4 타겟인 3번 노드는 중간값 이하이므로 왼쪽 노드에 존재 왼쪽 노드는 1~4까지의 값을 가진 노드, 중간값은 (1+4)//2 = 2 타겟인 3번 노드는 중간값 초과이므로 오른쪽 노드에 존재 오른쪽 노드는 3~4까지의 값을 가진 노드 ... 구간 곱..

https://www.acmicpc.net/problem/14503 구현 구현문제라 특벽한 로직은 없습니다. 문제에 맞게 북동남서를 설정(dr,dc) 왼쪽 회전 방향을 구하기 위해 나머지 연산 사용(nd = (d+3)%4) 2-1 조건에 부합할 경우에만 break를 걸어 첫번쨰 반복으로 돌아와서 청소 그 외의 경우에는 두번째 반복문에서 반복 변수에서 now를 사용했는데, 그냥 r,c,d로 직접 할당 했으면 이해가 더 쉬웠을거 같다 import sys # N = row , M = column N,M = map(int,sys.stdin.readline().split()) position = tuple(map(int,sys.stdin.readline().split())) arr = [list(map(int,s..

https://www.acmicpc.net/problem/1202 로직 보석을 무게순으로 정렬 가방을 무게 한도순으로 정렬 무게한도가 가장 낮은 가방부터 채우는 형식 현재 가방에 담을 수 있는 보석이면 can_theft에 heapq를 이용하여 추가(최대 값어치를 가진 보석이 pop되게 하기 위해) 현재 가방에 담을 수 있다면 다음 가방은 무게 한도가 더 크므로 다음 가방에도 담을수 있음 => can_theft를 유지 현재 가방에 담을 수 있는 보석이 모두 can_theft에 담기면 그 중 가장 큰 값어치를 가진 보석을 담음 import sys from heapq import heappush,heappop N,K = map(int,sys.stdin.readline().split()) jewel = [] f..

https://www.acmicpc.net/problem/18511 브루트포스 형식으로 경우의 수 구성 목표인 N과 동일한 자리수를 가진경우 목표인 N의 자리수보다 1 만큼 작은 경우(N = 100인데 사용 가능한 숫자가 9인경우 99를 만들기 위해) 이미 N값보다 커졌을 경우 가지치기 def check(i,total): global ans if total > N: return if i < 0 : if ans < total: ans = total return for num in nums[::-1]: # 디버깅 쉽게 하려고 [::-1] check(i-1,total+num*10**i) N,K = map(int,input().split()) n=len(str(N))-1 nums = list(map(int,in..

https://www.acmicpc.net/problem/1043 union을 이용 진실을 아는 경우 한 그룹으로 만듬 각 파티에 참석한 인원들을 같은 그룹으로 만듬 파티 참석 인원중 진실을 아는 사람이 있을 경우 진실을 아는 그룹과 union 되게 됨을 이용 def find(x): # 같은 그룹인지를 확인하는 함수, if par[x] == x: return x else: par[x] = find(par[x]) # dp스타일을 응용하여 최적화 return par[x] def union(a,b): # 유니온 함수 a = find(a) b = find(b) if size[a] size[b]: par[b] ..

https://www.acmicpc.net/problem/1149 앞 뒤 집과 색이 달라야 함, R G B 세가지 색을 사용하여 집을 색칠 집을 하나 칠하고 그 전집과 색이 다르게만 칠하면 자연스럽게 완성 최소 값을 구해야 하는데, 그 전집의 색, 지금까지의 값만 중요 DP를 이용하여 R,G,B색을 칠했을 경우 최소 비용을 누적하여 저장하는 형태 현재 집을 R 선택했다면, 전집이 G,B일때 값을 비교하여 둘 중 최소인 것만 저장 def check(i): for j in range(3): # 이번 집의 RGB 선택 pay = total[i][j] # 이번 집 색칠에 드는 비용 temp = [] for k in range(3): # 전집 색 선택 if k != j: # 같은색 배제 temp.append(dp..