bright

www.acmicpc.net/problem/1715

import heapq
import sys 
input = sys.stdin.readline 

n = int(input())
data = [] 
for i in range(n) : data.append(int(input()))
heapq.heapify(data)
result = 0 

while data:
  first = heapq.heappop(data)

  if len(data)<=0:   # 원소가 1개 이하일 때 
    break 
  
  second = heapq.heappop(data)
  heapq.heappush(data, first+second )
  result += first + second 

for i in data : 
  result += i 

print(result)

처음 더한 값들이 반복되어 더해지므로, 가장 작은 값부터 더해야한다. 

우선순위 큐를 이용해서 작은 값을 꺼낸다. 

www.acmicpc.net/problem/1238

import heapq
import sys
input = sys.stdin.readline 

n, m, x = map(int,input().split())
# n 명, 도로 m 개 , x 마을에서 

graph= [ [] for i in range(n+1)]
for i in range(m):
  a,b,c = map(int,input().split())
  graph[a].append((b,c))

def dij(start):
  q = []
  heapq.heappush(q, (0,start))
  dist = [1e9]*(n+1)
  dist[start] = 0 

  while q:
    d, now = heapq.heappop(q)
    if dist[now]<d : continue 
    for i in graph[now]:
      cost = d + i[1]
      if cost < dist[i[0]]:
        dist[i[0]] = cost 
        heapq.heappush(q,(cost,i[0]))
  return dist 

result = [0]
dist_x = dij(x)
for i in range(1,n+1):
  result.append( dij(i)[x] + dist_x[i] ) 

print ( max(result) )

www.acmicpc.net/problem/18352

import heapq
import sys
input = sys.stdin.readline 


n, m, k, x = map(int,input().split())
# 도시 도로 거리 출발 도시 
graph = [ [] for _ in range(n+1) ]
for i in range(m):
  a, b= map(int, input().split())
  graph[a].append(b)

# x에서 출발, 경로가 k 인 도시 오름차순 출력 없으면 -1 

def dij(start):
  q = []
  heapq.heappush(q, (0,start))
  dist = [1e9]*(n+1)
  dist[start]=0 

  while q:
    d, now = heapq.heappop(q)
    if dist[now]<d : continue 
    
    for i in graph[now]:
      cost = d + 1
      if cost<dist[i]:
        dist[i] = cost 
        heapq.heappush(q, (cost,i))
  return dist 

result = dij(x)
answer = []

for i in range(n+1) : 
  if result[i] == k : 
    answer.append(i)

if answer == [] : print(-1)
else:
  answer.sort()
  for i in answer: print(i)

www.acmicpc.net/problem/1504

import heapq
import sys
input = sys.stdin.readline

n, e = map(int,input().split()) # 정점, 간선 

graph=[ [] for _ in range(n+1) ]
for i in range(e): 
  a,b,c = map(int,input().split())
  graph[a].append((b,c))
  graph[b].append((a,c))

v1, v2 = map(int,input().split())

def dij(start):
  q = [] 
  heapq.heappush(q,(0,start))
  dist = [1e9]*(n+1)
  dist[start]=0 

  while q:
    d, now = heapq.heappop(q)
    if dist[now] < d : continue 

    for i in graph[now]:
      cost = d + i[1]
      if cost < dist[i[0]]:
        dist[i[0]] = cost 
        heapq.heappush(q, (cost,i[0]))
  return dist 


dist_1 = dij(1)
dist_v1 = dij(v1)
dist_v2 = dij(v2)

answer = min( dist_1[v1]+dist_v1[v2]+dist_v2[n], 
  dist_1[v2]+ dist_v2[v1]+dist_v1[n])

if answer >= 1e9 : 
  print(-1)
else : 
  print(answer)

주의사항 ) 

1. 양방향 그래프 => graph 에 추가할 때 앞 뒤로 다 해주기 

2. v1, v2 는 지나는 순서가 정해진 것은 x => 경우의 수 2개로 나누어서 더 작은 것으로 선택하기 

www.acmicpc.net/problem/1916

import heapq
import sys
input = sys.stdin.readline 

n = int(input()) # 도시 
m = int(input()) # 버스 

graph = [ [] for _ in range(n+1)]
for i in range(m):
  s,e,c = map(int,input().split())
  graph[s].append((e,c)) # 도착, 비용 

s, e = map(int,input().split()) # 출발 도착 

def dij(start):
  q = []
  dist = [1e9]*(n+1)
  heapq.heappush(q, (0,start) )
  dist[start]=0

  while q : 
    d, now = heapq.heappop(q)

    if dist[now]< d : continue 

    for i in graph[now]:
      cost = d + i[1]
      if cost < dist[i[0]]:
        dist[i[0]] = cost 
        heapq.heappush(q, (cost,i[0]))

  return dist 

result = dij(s)
print(result[e])

기본 다익스트라 구현법 사용! 

www.acmicpc.net/problem/9465

def sticker(n,data):

  data[0][1] += data[1][0] 
  data[1][1] += data[0][0] 

  for j in range(2,n):
    data[0][j] += max( data[1][j-2],  data[1][j-1] )
    data[1][j] += max ( data[0][j-2], data[0][j-1] )
  
  return max(data[0][n-1], data[1][n-1])

t = int(input())
t_print = []

for i in range(t):
  n = int(input())
  data = []
  for _ in range(2):
    data.append(list(map(int,input().split())))

  t_print.append ( sticker(n,data) )

for i in range(t):
  print( t_print[i] )

index 2 이상부터 2칸 전 대각선과 1칸 전 대각선 비교해서 더하기가 가능! 

# 11725

from collections import deque 

n = int(input()) # 노드의 수 

tree = [ [] for _ in range(n+1) ]
for i in range(n-1):
  a, b = map(int,input().split())
  tree[a].append(b)
  tree[b].append(a)

def bfs():

  q = deque()
  q.append(1)
  visited = [0] * (n+1)
  visited[1] = 1

  while q :
    x = q.popleft()
    for i in tree[x]:

      if visited[i] == False:
        visited[i] = x
        q.append(i)
  
  return visited
    
result = bfs()

for i in range(2,len(result)):
  print(result[i])

visited 리스트에 부모 노드를 저장함. 

1 -> 1과 연결된 것의 부모를 1로 설정하고 방문 처리한 뒤, queue에 넣음 -> 반복.. 

1. 시간 초과 코드 

# 2644

n = int(input()) # 전체 사람의 수 
a, b = map(int,input().split())
m = int(input()) # 관계의 수 

graph = [ [] for _ in range(n+1) ] 

for i in range(m):
  p, c = map(int,input().split())
  graph[p].append(c)

def bfs(x, y):
  p ,cnt = 0, 1

  while 1: 
    for i in range(1,n+1):
      if x in graph[i]:
        p = i 
        break 
    
    if p == 0 : return -1 
    else : cnt += 1 
    
    if y in graph[p] : return cnt 
    else : x = p  

print( bfs(a,b) ) 

2. 정답 코드 

# 2644
from collections import deque 

n = int(input()) # 전체 사람의 수 
a, b = map(int,input().split())
m = int(input()) # 관계의 수 

graph = [ [] for _ in range(n+1) ] 

for i in range(m):
  p, c = map(int,input().split())
  graph[p].append(c)
  graph[c].append(p)


def bfs(s, e):
  cnt = 0 
  queue = deque()
  queue.append(s) 
  visited = [False] * (n+1)  # 한 번 방문했는데 없던 곳 또 가지 않는다. 

  while queue:
    cnt += 1  # 한 단계 건널 때 마다 촌수 추가 
    
    for _ in range(len(queue)): # 지금 queue의 원소 만큼 반복 
      x = queue.popleft()

      if x == e : 
        return cnt-1
      
      for y in graph[x]:
        # 방문 안한 부분이 있으면 queue에 넣고 방문처리 
        if visited[y] == False:
          visited[y] = True 
          queue.append(y)
  
  return -1 

print( bfs(a,b) ) 

acmicpc.net/problem/2217

# 2217

n = int(input()) # 로프의 수 
data = []

for i in range(n):
  data.append(int(input()))

data.sort(reverse=True)

max_w = []

for i in range(n):
  max_w.append( data[i]*(i+1))

print(max(max_w))

너무 어렵게 생각하지 않는 것이 중요하다.

기본적으로 입력받은 중량 값을 역으로 정렬하여 사용한다. 

우선, 가장 기본적으로 들 수 있는 중량은 제일 큰 로프의 중량 값이다.

2가지의 로프를 사용한다면, 

가장 큰 로프는 그다음으로 큰 로프보다 항상 크므로 

두 번째 로프의 2배만큼의 중량을 들 수 있을 것이다. 

3가지의 로프를 사용하고.. 그 이상의 로프를 사용한다고 해도 마찬가지이다. 

이렇게 새로운 배열을 만들고 나서 가장 큰 값을 고르면 된다. 

www.acmicpc.net/problem/13305

# 13305 

n = int(input()) # 도시의 수 
dist = list(map(int, input().split() ))
cost = list(map(int, input().split() ))

# 처음 출발할 때, 무조건 기름 필요 
total = cost[0]*dist[0]
m = cost[0]

# 나보다 작은 값이 나오면 그 이후로 그 값으로 계산 
# 마지막 나라의 가격은 사실상 사용되지 않으므로 무시 가능 
for i in range(1,n-1):
  if cost[i] < m : 
    total += dist[i] * cost[i]
    m = cost[i]
  else : 
    total += dist[i]*m

print(total)

+) 주의사항 

만약에 계속 min 함수를 이용해서 최솟값을 찾고자 하면 시간 초과 오류가 날 수 있음. 

처음에 아래와 같이 코드를 작성했더니 시간 초과 오류가 남. 

# 13305 

n = int(input()) # 도시의 수 
dist = list(map(int, input().split() ))
cost = list(map(int, input().split() ))

# 처음 출발할 때, 무조건 기름 필요 
total = cost[0]*dist[0]

# 가장 작은 값 이후로는 다 작은 값으로 계산 
e = len(cost)
while e > 1 : 
  cost = cost[:e] 

  small = min(cost)
  s_i = cost.index(small)

  # print("최소값은", small, "index : ", s_i)

  for i in dist[s_i:e] :
    total += small* i
    #print('total: ', total)
    #print(dist[s_i:e])

  e = s_i

if e == 0 : 
  total -= cost[0]*dist[0]

print(total)