맛대의 블로그

https://www.acmicpc.net/problem/23793로직다익스트라 알고리즘 활용X에서 Z지점을 가는데, 1.Y지점을 거치는경우와 2.안거치는 경우를 계산1.Y지점을 거쳐야만 하는 경우 = X에서 Y로 가는 최단 경로 + Y에서 Z로 가는 최단경로2.Y지점을 거치면 안되는 경우 => Y node 도착시 우선순위 큐에 넣지 않는 형태로 구현(함수 인자 avoid)import sysfrom heapq import heappush,heappopinput = sys.stdin.readlinedef dijkstra(start:int,N:int,graph:list[tuple[int]],avoid=0)->list[int]: short_cut = [INF]*(N+1) short_cut[start..

https://www.acmicpc.net/problem/31713로직A: 줄기의 수, B: 잎의 수3*A 의 경우 추가적인 줄기와 잎의 수가 필요 없음저 범위에 해당하지 않는 경우에 추가적인 재료가 필요먼저 A가 많으면 모두 세잎클로버로 만듬(모든 줄기에 잎을 3개씩 붙이고, 남은 줄기*3만큼의 잎이 필요함)B가 많은 경우엔 네잎클로버 위주로 만들고, 줄기를 추가하여 세잎클로버 한두개를 섞는 방식으로 만들 수 있음하지만 이 경우 예시2번 tc 3번인 1 5가 주어질 경우 문제 발생줄기가 부족하여 A를 1 추가하여 2,5가 된 경우 다시 잎이 부족해짐그렇기에 B가 많은 경우의 조건을 먼저 체크 하여 A를 추가한 뒤, A가 많은 경우로 다시 체크import sysinput = sys.stdin.readli..

https://www.acmicpc.net/problem/20056로직구현문제파이어볼 이동과 파이어볼 병합 두가지로 구성된 문제격자의 시작과 끝이 연결되어 있으므로 나머지 연산 활용(%N)2개 이상 파이어볼이 있는 칸을 확인하기 위해 N*N 크기의 배열 사용(변수명 arr)파이어볼이 병합되는 경우 방향 계산을 위해 비트연산 사용(방향%2) 계산시 짝수, 홀수에 따라 0과 1의 값이 나옴여기에 1을 더하면 짝수는 1, 홀수는 2의 값방향(변수명 diretion)을 이 값과 AND연산모두 홀수 방향인 경우 값은 2, 모두 짝수 방향인 경우 값은 1, 홀짝 모두 있을 경우 값이 3이 되는 것을 활용실수했던 것입력값이 주어질 때 부터 스피드를 격자크기로 나머지 연산을 해버렸는데, 이 경우 파이어볼 병합 시 스피..

https://www.acmicpc.net/problem/5212로직단순 구현 문제땅의 상하좌우를 탐색해서 바다가 3면 이상이면 list에 기록(바다로 한번에 바꾸기 위해)바로 바다로 바꾸면 주변에 있는 땅에도 영향이 미치기에지도의 상단,하단에서 땅이 있는지 확인하고, 모두가 바다면 ''로 변경def clearArrRow(R,C,arr,asc): range_r = range(R) if asc else range(R-1,-1,-1) flag = True for r in range_r: if flag == False: break for c in range(C): if arr[r][c] == groundSign: flag ..

https://www.acmicpc.net/problem/14620로직입력값으로 땅값이 주어짐땅값을 기준으로 row,column 위치에 씨앗을 심을 경우 필요한 비용을 계산계산된 비용을 정렬(낮은 비용부터 탐색 하기 위해)3개의 값을 선택 후, 근처에 있는지(꽃 잎이 겹쳐 시드는지)를 체크이를 이용하여 값 갱신, 갱신된 값으로 백트레킹def costCheck(N:int,arr:list[list[int]])->list[tuple[int]]: newArr = list() for r in range(N): for c in range(N): num = arr[r][c] for nr,nc in ((r+1,c),(r-1,c),(r,c-1),(r,c+1)..

https://www.acmicpc.net/problem/2056문제 해석작업에는 선행되어야 할 작업이 있다작업들은 정렬이 잘 되어 있어 K번 작업에 필요한 선행작업은 K-1번째 작업 이하로만 구성되어 있다그렇기에 graph를 그려 선행 작업들을 기록해둘 필요가 없다1번부터 N번까지 작업들을 순회해당 작업에 필요한 시간 + 선행 작업이 완료되는데 걸리는 시간을 구한다import sysinput = sys.stdin.readlineN = int(input())check = [0]*(N+1)for node in range(1,N+1): time,P,*works = map(int,input().split()) if P: added_time = 0 for work in wor..

https://www.acmicpc.net/problem/1113로직구현, dfs땅의 높이가 1~9사이의 값이므로 각 경우에 물을 얼마나 담을 수 있는 지 확인for h in range(1,10)지금 생각해보니 range(2,10)이 맞는 것 같다물의 높이가 h일때 물에 잠기는 구역 확인(h보다 낮은 구역)물에 잠기는 구역 중에서 물이 바깥으로 넘치는 구역을 체크temp를 R*C 2중배열에 0~2의 값을 할당0은 그 구역의 땅이 물의 높이보다 높거나 같다1은 그 구역의 땅이 물의 높이보다 낮다2는 방문 체크를 위해 사용하는 값, 1인 구역을 탐색 완료시 2로 변경def solution(R:int,C:int,arr:list[list[int]])->int: dr,dc = (0,0,-1,1),(1,-1,..

https://www.acmicpc.net/problem/17484로직왼쪽 대각선, 아래, 오른쪽 대각선으로 이동하는 경우를 따로 기록이동시 최소의 값만 이용하여 연산을 줄임이 떄 필요한 최소의 값은 바로 위칸의 값이니 row를 2칸으로 만들어 메모리 낭비를 줄임N,M = map(int,input().split())arr = [list(map(int,input().split())) for _ in range(N)]inf = 601record = [[[0]*3 for i in range(M+1)] for _ in range(2)]for i in range(3): record[0][M][i] = inf record[1][M][i] = infp = 0for r in range(N): np = ..

https://www.acmicpc.net/problem/13913로직bfs 활용방문 체크를 dict를 활용하여 경로 추적까지 처리방문 체크(record)를 dictionary로 생성key값이 있으면 방문했던 지점, value는 해당 지점을 어디서 왔는지1 -> 2 -> 4로 이동했다고 가정{1:-1, 2:1, 4:2}로 기록됨, -1은 시작점을 체크하기 위한 것코드from collections import dequedef path(S:int, dictionary:dict)->str: path_list = [] point = S while point != -1: path_list.append(str(point)) point = dictionary[point] ..

https://www.acmicpc.net/problem/2469로직구현문제모르는 줄(?????)을 기준으로 그 위에선 어떻게 진행되는지, 그 아레에선 어떻게 진행되는지 계산(check함수)사다리의 정보를 기준으로 이동을 기록예를들어 [A,B,C,D] 로 출발하여 [B,A,C,D] 로 완성될 경우 [1,0,2,3] 으로 기록됨[1,0,2,3]의 경우 0번 인덱스가 1번으로, 1번 인덱스 0번으로, 2,3번은 그대로를 의미이렇게 위 아래를 계산 후 col이 0번부터 현재 사다리에 가로막대가 없을 경우 값을 계산계산된 값이 결과와 다르면 사다리가 있어야함을 의미이 때 사다리가 있을 경우 +1번과 자리가 변경됨전에 이동이 필요해서 -를 두었는데, 또 이동이 필요한 경우 해당 문제에선 불가능한 경우의 수def ..