one Book a Day

https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net fireball data를 어떻게 다룰것이냐? 나는 deque를 써서 반복문을 진행했고 중간에 이동연산은 dictionary를 이용해 각 속성을 모아줬다. 한번에 통과. import sys input = sys.stdin.readline from collections import deque def bfs(): cnt = 0 while fireballs: fi..

dfs로 통과시키긴 했는데 다른분들 답보니 그냥 w/리프노드의 수 이게 답이더라. 생각해보니 내 답도 결국 (총 물의 양)/(리프노드의 수) 이거였는데.. 통과된게 신기할 따름.. import sys input = sys.stdin.readline sys.setrecursionlimit(10**6) def dfs(cur_node, water): visited[cur_node] = True n = len(tree[cur_node])-1 if not n: ans.append(water) return unit = water/n for next_node in tree[cur_node]: if not visited[next_node]: dfs(next_node,unit) N, W = map(int, input()..

정렬해 작은 순으로 먹으면 되는 간단한 문제. import sys input = sys.stdin.readline N, L = map(int, input().split()) h_arr = list(map(int, input().split())) h_arr.sort() for h in h_arr: if L >= h: L += 1 continue break print(L)

https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net LCS에서 연속성만 부여하면 된다. 같을때 대각선 위값을 계승. 틀릴때 그냥 0 import sys input = sys.stdin.readline str1, str2 = (input().rstrip() for _ in range(2)) n, m = len(str1), len(str2) dp = [[0]*(m+1) for _ in range(n+1)] max_v = 0 for i in ..

말 그대로 귀찮은 문제. 하지만 많이 보던 파일 합치기의 idea가 일부 사용된 문제기도 하다. 가장 작은 부분부터 해결하는게 최소 비용을 보장한다. import sys input = sys.stdin.readline n = int(input()) arr = list(map(int, input().split())) arr.sort() total = sum(arr) answer = 0 for num in arr: answer += num * (total - num) total -= num print(answer)

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 참 묘한게 처음풀때는 이게 골드4인가 싶었는데 이제는 쉽다. 디버깅 몇 번하고 통과. 전에 푼것보다 훨씬 빠른 코드다. import sys input = sys.stdin.readline from collections import deque def eat_fish(fish, s, c): fish.sort() x, y = fish[0] aquarium[x][y] = 0 c += 1 if c=..

https://www.acmicpc.net/problem/2058 2058번: 원자의 에너지 잘 알려져 있듯, 각각의 원자들은 어떤 특정한 에너지 상태(혹은 에너지 준위)에 놓일 수 있다. 각각의 상태는 그 상태에서 그 원자가 갖는 에너지로 나타낼 수 있다. 어떤 원자가 높은 에너지 상 www.acmicpc.net tree_DP기본문제다.. 근데 안풀린다.. 다른문제로 연습하고 다시 도전할 것. 문제를 이해 못한건지 그냥 안풀린다.// 풀었음 정렬해서 한쪽 끝에서만 더하면 될 줄 알았는데 반례가 많은 것같다. 모든 시작지점에서 부터 돌렸다. 다시풀었는데 그냥 양성자를 빼는 경우만 고려해주면 시작점에서만 시작하면 되더라. 시간 500 -> 140 -> 120 까지 줄이고 종료. +gap만 조사 import..

LCS는 실상 냅색이랑 다를바가 없는 것 같다. 하지만 매우 중요한 개념. import sys input = sys.stdin.readline s1, s2, s3 = (input().rstrip() for _ in range(3)) n1, n2, n3 = len(s1), len(s2), len(s3) dp = [[[0 for _ in range(n1+1)] for _ in range(n2+1)] for _ in range(n3+1)] for i in range(n1): for j in range(n2): for k in range(n3): if s1[i] == s2[j] == s3[k]: dp[k+1][j+1][i+1] = dp[k][j][i] + 1 else: dp[k+1][j+1][i+1] = max..

조건이 2개인 0-1 knapsack. 3차원인데 조정하면 2차원까지 가능. order를 1개씩 늘려가며 그 order를 가져가는것과 가져가지 않는것중 max가 큰것을 들고간다. import sys input = sys.stdin.readline N, M, K = map(int, input().split()) orders = [[0, 0]] + [list(map(int, input().split())) for _ in range(N)] dp = [[[0 for _ in range(K + 1)] for _ in range(M + 1)] for _ in range(N + 1)] for order_cnt in range(1, len(orders)): cur_b, cur_f = orders[order_cnt] ..

https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 파이프가 대각선으로 움직일때 벽을 긁으면 안된다. 즉 벽이있으면 대각선 처리를 하지 않는다. import sys input = sys.stdin.readline N = int(input()) house = [list(map(int, input().split())) for _ in range(N)] # 오른쪽에서 오거나 왼쪽에서 오거나 대각선으로 오는 경우의 dp dp = ..