흙금이네 블로그

아이디어 투 포인터를 이용하여 동시에 가지고 있는 CD의 개수를 구한다. 풀이 import sys input = sys.stdin.readline def solution(): while 1: N, M = map(int, input().split()) if N == 0 and M == 0: break CD1 = [int(input()) for _ in range(N)] CD2 = [int(input()) for _ in range(N)] res = i = j = 0 while i CD2[j]: j += 1 else: i += 1 print(res) solution()

아이디어 이분 탐색으로 N의 제곱근을 찾는다. 풀이 def solution(): N = int(input()) s = 1 e = N while 1: m = (s+e)//2 if m**2 > N: e = m-1 elif m**2 < N: s = m+1 else: print(m) return solution()

아이디어 조건에 따라 주사위가 이동할 때마다 주사위와 지도의 상태를 변경한다. 풀이 import sys input = sys.stdin.readline delta = [(0, 1), (0, -1), (-1, 0), (1, 0)] dice = [0]*6 turned = [ (3, 1, 0, 5, 4, 2), (2, 1, 5, 0, 4, 3), (4, 0, 2, 3, 5, 1), (1, 5, 2, 3, 0, 4) ] def solution(): N, M, x, y, K = map(int, input().split()) board = [list(map(int, input().split())) for _ in range(N)] for d in map(int, input().split()): d -= 1 nx, ..

아이디어 재귀를 통해 계산에 필요한 수들을 구해 나간다. 풀이 def find_A(i): if A.get(i, 0): return A[i] A[i] = find_A(i//P)+find_A(i//Q) return A[i] N, P, Q = map(int, input().split()) A = dict() A[0] = 1 print(find_A(N))

아이디어 유니온 파인드를 이용하여 상호 배타적 집합의 개수를 구하고, 집합 내 최소 비용의 합을 구한다. 풀이 import sys input = sys.stdin.readline def solution(): for _ in range(M): v, w = map(int, input().split()) union(v, w) for i in range(1, N+1): find(i) res = 0 for i in set(group): res += A[i] if res w: v, w = w, v group[w] = v if A[w] < A[v]: A[v] = A[w] N, M, k = map(int, input().split()) A = [0]+list(map(int, input().split())) group ..

아이디어 탄산 내성 K보다 큰 2의 거듭제곱의 개수를 구하고, 이변을 통해 승리할 수 있는 횟수를 더한다. 풀이 def solution(): N, M, K = map(int, input().split()) n = 1 res = 0 while n < N: n *= 2 if K < n: if M == 0: break M -= 1 res += 1 print(res) solution()

아이디어 최솟값을 찾는 우선순위 큐, 최댓값을 찾는 우선순위 큐, 남은 값의 개수를 저장하는 딕셔너리를 사용하여 해결한다. 풀이 우선순위 큐를 사용하기 위해 heapq 모듈의 heappush와 heappop을 불러온다. 최댓값을 저장하는 우선순위 큐 max_heap과 최솟값을 저장하는 우선순위 큐 min_heap을 생성하고, 남은 데이터의 총 개수 total, 남은 값의 개수를 저장하는 딕셔너리 cnt_dict를 생성한다. k번의 for문에서 연산이 I이면 cnt_dict를 참고해 추가하려는 값의 남은 개수가 0이면 min_heap과 max_heap에 추가하고, 그렇지 않으면 두 우선순위 큐에 추가하지 않고 cnt_dict의 값과 total을 1 증가시킨다. 연산이 D이면 cnt_dict를 참고해 남은 ..

아이디어 BFS로 건물 내부와 외부를 구분한 후, 외부에 보이는 벽면의 수를 구한다. 풀이 #1 (Python) 문제의 정육각형 좌표 값 y가 홀수일 때를(인덱스 기준 짝수) 기준으로 위치 변화 값들을 튜플로 리스트 delta에 저장한다. 지도의 너비 W, 지도의 높이 H를 입력 받고, 집의 건물 배치를 2차원 리스트 buildings에 저장한다. 지도 가장자리 부분의 좌표들을 인자로 함수 bfs를 호출하여 건물 내부와 외부를 구분한다. 인덱스가 홀수인 행이면서 행의 위치가 변하면 delta에서 열 변화 값을 1을 감소시켜 위치 변화 값을 조정한다. 함수 bfs 호출로 지도 buildings에서 외부 공간은 -1, 내부 공간에서 건물이 있는 곳은 1, 없는 곳은 0의 값을 갖게 된다. 이후 건물이 있는 ..

아이디어 BFS로 공주에게 도달하는 최단 시간을 구하고, T시간 이내에 도달할 수 있는지 확인한다. 풀이 #1 (Python) 방문 표시 및 각 칸에 도달하는 최단 시간 저장을 위해 N×M 크기의 0으로 채워진 2차원 리스트 visited를 생성한다. 출발 위치는 성의 구조 castle에서 1로 저장하여 다시 방문하지 않도록 하고, 도착 위치는 visited에서 T+1로 저장한다. 큐 queue에 출발 위치를 저장하고 while문에서 delta를 통해 BFS로 성을 탐색한다. 다음 칸이 도착 위치인 경우 도달 시간을 최솟값을 저장하고 큐 queue를 비운 후 break로 while문을 종료한다. 다음 칸이 도착 위치가 아니고 방문하지 않은 칸이라면 elif문으로 진입한다. 방문하는 칸이 빈 공간이라면 방..

아이디어 BFS로 1번 헛간과 거리가 가장 먼 헛간들을 찾는다. 풀이 #1 (Python) 방문 표시 및 1번 헛간과의 거리를 저장하기 위해 N+1 크기의 0으로 채워진 리스트 visited를 생성한다. visited에서 1번 헛간의 값을 1로 저장하고, 큐 queue에 1을 저장한다. while문에서 BFS로 방문하지 않은 주변 헛간으로 이동하며 visted에 1번 헛간과의 거리보다 1 더 큰 값을 저장한다. 모든 헛간을 방문한 후 for문에서 숨어야 하는 헛간 번호 num, 해당 헛간까지의 거리 d, 같은 거리의 헛간 수 cnt를 구한다. import sys input = sys.stdin.readline def solution(): N, M = map(int, input().split()) grap..