n = int(input())
# 회의 정보를 담을 리스트
array = []
for _ in range(n):
# 시작 시간, 끝나는 시간, 회의 인원 입력
array.append(list(map(int, input().split())))
# 시작 시간 기준 오름차순 정렬
array.sort()
dp = [0] * n
dp[0] = array[0][2]
for i in range(1, n):
dp[i] = max(dp[i - 1], dp[i - 2] + array[i][2])
print(dp[n - 1])
import sys
input = sys.stdin.readline
k = int(input())
x, y = map(int, input().split())
num = 0
length = pow(2, k)
map = [[0] * length for _ in range(length)]
map[x - 1][y - 1] = -1
def checkHole(x, y, len):
for i in range(x, x + len):
for j in range(y, y + len):
if map[i][j] != 0:
return False
return True
def tromino(x, y, len):
num += 1
halfLen = len // 2
if (checkHole(x, y, halfLen)):
map[x + halfLen - 1][y + halfLen - 1] = num
if (checkHole(x, y + halfLen, halfLen)):
map[x + halfLen - 1][y + halfLen] = num
if (checkHole(x + halfLen, y, halfLen)):
map[x + halfLen][y + halfLen - 1] = num
if (checkHole(x + halfLen, y + halfLen, halfLen)):
map[x + halfLen][y + halfLen] = num
if halfLen == 2:
return
tromino(x, y, halfLen)
tromino(x, y + halfLen, halfLen)
tromino(x + halfLen, y, halfLen)
tromino(x + halfLen, y + halfLen, halfLen)
tromino(0, 0, length)
for i in range(length):
for j in range(length):
print(map[i][j], end=' ')
print()
import sys
input = sys.stdin.readline
# 테스트 케이스 수만큼 반복
for t in range(int(input())):
n = int(input())
data = []
for _ in range(n):
x, y = map(int, input().split())
data.append([x,y])
data.sort()
count = 0
min = [data[0][0], data[0][1]]
for i in range(1, n):
if data[i][0] > min[0]:
min[0] = data[i][0]
if data[i][1] > min[1]:
min[1] = data[i][1]
count += 1
print(n - count)
n = int(input())
time = []
for _ in range(n):
a, b = map(int, input().split())
# 끝나는 시간, 시작 시간 순으로
time.append([b,a])
# 끝나는 시간을 기준으로 오름차순 정렬
time.sort()
count, end = 0, 0
for i in time:
# 직전 회의랑 겹치지 않으면 선택
if end <= i[1]:
count += 1
end = i[0]
print(count)
시간복잡도는 정렬 때문에 O(NlogN)입니다. 부족한 부분은 말해주시면 감사하겠습니다 :)
def solution(n, lost, reserve):
answer = n - len(lost)
# 여벌 체육복이 있는 학생이 체육복을 도난당했을 경우
for i in reserve:
if i in lost:
answer += 1
lost.remove(i)
reserve.remove(i)
reserve.sort()
lost.sort()
for i in lost:
for j in reserve:
if -1 <= i - j <= 1:
answer += 1
reserve.remove(j)
break
return answer
import heapq
INF = int(1e9)
def dijkstra(start):
q = []
# 시작 노드까지의 최단 경로를 0으로 설정하고, 큐에 삽입
heapq.heappush(q, (0, start))
distance[start] = 0
# 큐가 빌 때까지
while q:
dist, now = heapq.heappop(q)
# 이미 처리된 노드 무시
if dist > distance[now]:
continue
for i in graph[now]:
cost = dist + i[1]
# 현재 노드를 거쳐서 가는 경로가 더 짧은 경우
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q, (cost, i[0]))
# 정점의 개수 V, 간선의 개수 E 입력
V, E = map(int, input().split())
# 시작 정점 K
k = int(input())
# 최단 거리 테이블 INF로 초기화
distance = [INF] * (V + 1)
# 방향그래프 정보를 담는 리스트
graph = [[] for _ in range(V + 1)]
for _ in range(E):
# u에서 v로 가는 가중치 w
u, v, w = map(int, input().split())
graph[u].append((v, w))
# 다익스트라 수행
dijkstra(k)
# 각 정점으로의 최단 경로값 출력
for i in range(1, V + 1):
if distance[i] == INF:
print('INF')
else:
print(distance[i])
💡해결 방법 - 아래 코드 추가
import sys input = sys.stdin.readline
내 풀이😊
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)
def dijkstra(start):
q = []
# 시작 노드까지의 최단 경로를 0으로 설정하고, 큐에 삽입
heapq.heappush(q, (0, start))
distance[start] = 0
# 큐가 빌 때까지
while q:
dist, now = heapq.heappop(q)
# 이미 처리된 노드 무시
if dist > distance[now]:
continue
for i in graph[now]:
cost = dist + i[1]
# 현재 노드를 거쳐서 가는 경로가 더 짧은 경우
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q, (cost, i[0]))
# 정점의 개수 V, 간선의 개수 E 입력
V, E = map(int, input().split())
# 시작 정점 K
k = int(input())
# 최단 거리 테이블 INF로 초기화
distance = [INF] * (V + 1)
# 방향그래프 정보를 담는 리스트
graph = [[] for _ in range(V + 1)]
for _ in range(E):
# u에서 v로 가는 가중치 w
u, v, w = map(int, input().split())
graph[u].append((v, w))
# 다익스트라 수행
dijkstra(k)
# 각 정점으로의 최단 경로값 출력
for i in range(1, V + 1):
if distance[i] == INF:
print('INF')
else:
print(distance[i])
전에 풀었던 C++코드와 메모리/시간을 비교했을 때, 확실히 파이썬이 훨씬 더 많이 잡아먹긴 하네요ㅜㅜ
# 정수 N 입력
n = int(input())
# DP 테이블 초기화
dp = [0] * (n + 1)
# 다이나믹 프로그래밍 - 보텀업
for i in range(2, n + 1):
# 1 빼기 연산 수행
dp[i] = dp[i - 1] + 1
# 3으로 나누어 떨어지는 경우
if i % 3 == 0:
dp[i] = min(dp[i], dp[i // 3] + 1)
# 2로 나누어 떨어지는 경우
if i % 2 == 0:
dp[i] = min(dp[i], dp[i // 2] + 1)
print(dp[n])
# N 입력
n = int(input())
# DP 테이블 0으로 초기화
dp = [0] * (n + 1)
dp[3] = 1
if n >= 5:
dp[5] = 1
for i in range(6, n + 1):
# i-5킬로그램을 만들 수 있을 경우
if dp[i - 5] != 0:
dp[i] = dp[i - 5] + 1
# i-3킬로그램을 만들 수 있을 경우
elif dp[i - 3] != 0:
dp[i] = dp[i - 3] + 1
if dp[n] == 0:
print(-1)
else:
print(dp[n])
먼저 일반적인 DFS, BFS 코드를 짜고 문제에서 정점 번호가 작은 것부터 방문하라고 되어있길래
dfs부터 코드를 고쳤습니다.
list = graph[start]
list.sort()
근데 이 코드 하나 dfs에 넣었더니 bfs까지 같이 결과가 바뀌더군요,,,
파이썬을 시작한 지 얼마 안돼서 문법을 잘 몰랐었는데 리스트 부분을 조금 더 공부해야겠어요!
내 풀이😊
from collections import deque
# 깊이 우선 탐색 DFS
def dfs(graph, start, visited):
visited[start] = True
print(start, end=' ')
# 정점 번호가 작은 것부터 방문
list = graph[start]
list.sort()
for i in list:
if visited[i] == False:
dfs(graph, i, visited)
# 넓이 우선 탐색 BFS
def bfs(graph, start, visited):
queue = deque()
queue.append(start)
visited[start] = True
print(start, end=' ')
# 큐가 빌 때까지
while queue:
x = queue.popleft()
for i in graph[x]:
if visited[i] == False:
queue.append(i)
visited[i] = True
print(i, end=' ')
# 정점의 개수 N, 간선의 개수 M, 탐색을 시작할 정점의 번호 V 입력
n, m, v = map(int, input().split())
# 간선이 연결하는 두 정점의 번호
graph = [[] for _ in range(n + 1)]
for i in range(m):
x, y = map(int, input().split())
# 간선은 양방향
graph[x].append(y)
graph[y].append(x)
visited = [False] * (n + 1)
# DFS 실행
dfs(graph, v, visited)
print()
visited = [False] * (n + 1)
# BFS 실행
bfs(graph, v, visited)
