맛대의 블로그

로직설명을 어떻게 해야할까...커멘드는 E,W 두가지왼쪽부터 탐색시 E로 진행하다가, W를 만나는 순간 흐름이 바뀜W를 만나는 순간 선물을 하나 둬야함하지만 그 전칸도 W일 경우 추가 선물이 필요 없음def solution(N:int,cmds:str)->int: idx,cnt = 0,0 for idx in range(N): if cmds[idx] =='W' and cmds[idx-1] == 'E': cnt += 1 return cntN = int(input())cmds = input()ans = solution(N,cmds)print(ans)

https://www.acmicpc.net/problem/23801로직다익스트라 알고리즘시작 지점에서 각 지점까지의 최소 거리를 구할 수 있음X지점 - P개의 중간 정점 중 한 지점 - Z지점 으로 이동X에서 다익스트라 = X부터 P에 속한 모든 지점 까지의 최단 거리 계산 가능Z에서 다익스트라 = Z부터 P에 속한 모든 지점 까지의 최단 거리 계산 가능모든 P에 속한 지점(p)에 대해서 X->p->Z의 값 = X->p + Z->pfrom heapq import heappush,heappopimport sysinput = sys.stdin.readlinedef dijkstra(start:int,N:int,graph:list[tuple[int]])->list[int]: INF = float('inf'..

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 = ..