본문 바로가기

백준8

[파이썬] 백준 2156번: 포도주 시식 N = int(input()) wine = [0] maxi = [0]*(N+1) for i in range(1, N+1): wine.append(int(input())) if i < 3: maxi[i] = sum(wine) else: target = [] target.append(maxi[i-3]+wine[i-1]+wine[i]) target.append(maxi[i-2]+wine[i]) target.append(maxi[i-1]) maxi[i] = max(target) print(maxi[-1]) 다이나믹 프로그래밍 문제다. 처음에 DFS로 풀었는데 시간초과가 떠서 다시 풀었다. 포도주가 1잔 또는 2잔이 있을 때에는 그냥 모두 다 마시면 된다. 하지만 3잔째 부터는 선택을 해야 한다. 선택에는 3가지.. 2020. 6. 9.
[파이썬] 백준 17140번: 이차원 배열과 연산 def func(B, ga, se): # 가로로 한 줄씩 연산 실행하고 결과 반환 newlist = [[] for _ in range(ga)] # 저장할 리스트 maxi = 0 # 세로 최대값을 갱신 for i in range(ga): mydict = dict() # 라인 별 숫자를 세기 위한 딕셔너리 for j in range(se): if B[i][j] != 0: # 0은 무시한다 if B[i][j] in mydict: # 값이 있을 경우 +1 한다 mydict[B[i][j]] += 1 else: # 값이 없을 경우 1을 배치한다 mydict[B[i][j]] = 1 mylist = list(mydict.items()) # (key, value) 저장 mylist.sort(key=lambda x: (x.. 2020. 5. 28.
[파이썬] 백준 9251번: LCS 이 문제는 코드가 간단하지만 설명이 필요할 것 같아서 알고리즘을 시각화 시켜보았다. import copy A = input() B = input() mylist = [0]*len(B) for a in A: sublist = copy.deepcopy(mylist) for b in range(len(B)): if B[b] == a: if b != 0: target = max(mylist[:b]) else: target = 0 sublist[b] = target+1 mylist = sublist print(max(mylist)) 2020. 5. 25.
[파이썬] 백준 6593번: 상범 빌딩 from collections import deque dh = [-1, 1, 0, 0, 0, 0] # 상하좌우앞뒤 dx = [0, 0, 0, 0, 1, -1] dy = [0, 0, -1, 1, 0, 0] def BFS(h, x, y): # h: 높이, x: 앞뒤, y: 좌우 global answer for d in range(6): H = h + dh[d] X = x + dx[d] Y = y + dy[d] if 0 2020. 5. 18.
[파이썬] 백준 17136번: 색종이 붙이기 def DFS(x, y): global answer if board[x][y] == 1: # 해당 칸에 1이 적혀있으면 for k in range(5, 0, -1): # 5부터 1까지 if mydict[k] > 0 and x+k 2020. 5. 7.
[파이썬] 백준 11559번: Puyo Puyo from collections import deque dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] def BFS(x, y): for d in range(4):# 상하좌우 X = x + dx[d] Y = y + dy[d] if 0 2020. 5. 5.

티스토리툴바