bright

www.acmicpc.net/problem/1743

from collections import deque

n, m , k = map(int,input().split()) # 세로 가로 음식물 수 
graph = [ [0]*m for i in range(n)]
for i in range(k):
  a,b = map(int,input().split())
  graph[a-1][b-1] = 1 


dx = [-1,1,0,0]
dy = [0,0,1,-1]

def bfs(x,y):
  q = deque()
  q.append((x,y))
  graph[x][y] = 0 
  cnt = 1 

  while q : 
    a, b= q.popleft()
    for i in range(4):
      nx = a + dx[i]
      ny = b + dy[i]

      if nx<0 or nx>=n or ny<0 or ny>=m : 
        continue 
      if graph[nx][ny] == 1:
        cnt += 1 
        q.append((nx,ny))
        graph[nx][ny] = 0 
  return cnt 

tmp = 0 

for i in range(n):
  for j in range(m):
    if graph[i][j] != 0 :
      tmp = max(tmp, bfs(i,j))

print(tmp)

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)

www.acmicpc.net/problem/4796

# 4796

data = [] 
while True : 
  L, p, v = map(int, input().split() ) 
  if L + p + v == 0 : 
    break 
  else : 
    data.append([L,p,v])

for i in data : 
  L, p, v = i[0], i[1], i[2]

  cnt = ( v//p )*L
  re = v - p*(v//p)

  if re <= L :
    cnt += re
  else : 
    cnt += L
  
  print("Case",str(data.index(i)+1)+":",cnt)

# (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19) 

year = list(map(int,input().split()))

for result in range(1,7981):
  if result % 15 == year[0] or ( result%15 == 0 and year[0] == 15 ) :
    if result % 28 == year[1] or (result%28 == 0 and year[1] == 28 ) :
      if result % 19 == year[2] or ( result%19 == 0 and year[2] == 19) :
        print(result)

문제에 보면 주어진 시간이 2초로 긴 편이다. 

완전 탐색으로 접근해서 풀어도 무방하다. 

주의! 15/28/19 로 나누어 떨어지면 나머지는 0 이지만 표현되는 수는 15 임을 조심! 

# 난쟁이 키 합이 100 
from itertools import combinations 

height = [] 
for i in range(9):
  height.append(int(input()))

height.sort() 

combi = list(combinations(height,7))

for i in combi : 
  h_sum = 0 
  for k in range(7):
    h_sum += i[k]
  
  if h_sum == 100 : 
    result = i 
    break 

for k in range(7):
  print(result[k])

조합 ( combination ) 모듈을 통해 완전 탐색으로 풀이한다. 

조합의 결과는 튜플로 나옴에 유의한다. 

from itertools import combinations 

combi = list( combinations( 조합을 사용할 list , 조합할 단위 )) 

+ ) 순열은 순서가 의미 있는 조합이며, permutations 로 사용한다. 

S = input()
count = 1
for i in range(len(S)-1):
    if S[i] != S[i+1]:
        count += 1
print( count//2 )

바뀌는 것을 세면, 실제 바뀐 것은 1번 인데 앞, 뒤로 카운트 되기 때문에 마지막에 2로 나누어 준다. 

처음 시작 할 때 바뀌는 것은 1 번만 카운트 되므로 count = 1 부터 시작한다.