코딩기록

https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net N, C = map(int, input().split()) house = [int(input()) for _ in range(N)] house.sort() # 오름차순 정렬 low, high = 1, house[-1] - house[0] while low = cur + mid: cur = house[i] count += 1 if count >= ..

https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net import sys, heapq # 동서남북 dx = [0, 0, -1, 1] dy = [1, -1, 0, 0] count = 1 # 순서 def dijkstra(): queue = [] heapq.heappush(queue, (graph[0][0], 0, 0)) # 시작 노드 큐에 삽입 dist[0][0] = graph[0][0] while queue: cur_dist, x, ..

https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 이 문제를 처음 보면 그래프 문제일 것이라고 쉽게 생각나지 않는다. 문제의 예시를 자세히 살펴보면 왜 이 문제가 그래프 문제인지 알 수 있다. 그 이유는 다음 그림을 참고하면 된다. from collections import deque F, S, G, U, D = map(int, input().split()) dist = [0] * (F+1) # 방문 확인 리스트 def bfs(start): queue = d..

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net from collections import defaultdict import sys, heapq input = sys.stdin.readline V, E = map(int, input().split()) # 정점, 간선 개수 start = int(input()) # 시작 노드 graph = defaultdict(list) # 방향 그래프 dist = [sys...

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net from collections import deque m, n = map(int, input().split()) # 가로, 세로 graph = [list(map(int, input().split())) for _ in range(n)] # 토마토 정보 # 동서남북 이동 방향 dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] queue = deque() answer..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net n = int(input()) # 지도 크기 graph = [list(map(int, input())) for _ in range(n)] # 지도 answer = [] # 단지 내 집의 수 리스트 count = result = 0 # 각 단지내 집의 수, 총 단지 수 dx = [-1, 0, 1, 0] dy = [0, -1, 0, 1] def dfs(x, y): if x = n or y = n: # ..

https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net [ 실패 코드 ] - 시간 초과 시간 초과의 이유를 살펴보니 index, slicing 을 사용하면 시간 초과가 났다고 한다. 나는 둘 다 사용하지 않았지만 시간초과가 났다. 뒤에서부터 비교 -> 앞에서부터 비교로 바꾸고 코드 구성을 바꿔줬더니 통과하였다. 시간초과...해결하기 너무 어렵다.... n = int(input()) towers = list(map(int, input().split()..

https://www.acmicpc.net/problem/5567 5567번: 결혼식 예제 1의 경우 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2, 3, 4 3명의 친구를 결혼식에 초대 www.acmicpc.net n = int(input()) m = int(input()) graph = [[] for _ in range(n+1)] visited = [0] * (n+1) # 방문 확인 및 관계 구분 리스트 # 친구 관계 입력받기 for _ in range(m): a, b = map(int, input().split()) graph[a].append(b) graph[b].append(a) # B..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net n = int(input()) dp = [0] * (n+1) for i in range(2, n+1): dp[i] = dp[i-1] + 1 # 2와 3으로 나누어 떨어지지 않는 경우 무조건 1을 빼줘야 하므로 횟수를 추가한다 if i % 2 == 0: # 2로 나누어 떨어지는 경우 dp[i] = min(dp[i], dp[i//2] + 1) if i % 3 == 0: # 3으로 나누어 떨어지는 경우 dp[i] = min(dp[i], dp[i//3] + 1) print(dp[n]) 이 문제는 그렇게 어렵지 않은 d..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net n = int(input()) wine = [0] + [int(input()) for _ in range(n)] dp = [0] * (n+1) if n == 1: print(wine[1]) else: dp[1] = wine[1] dp[2] = wine[1] + wine[2] # 최대로 마실 수 있는 포도주의 양 구하기 for i in range(3, n+1): dp[i] = max(dp[i-1], ..