one Book a Day

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 = ..

들어오는 두 점이 모두 동일한 집합에 속한 점이라면 사이클이 형성된다. import sys input = sys.stdin.readline def find(x): if x == arr[x]: return x arr[x] = find(arr[x]) return arr[x] def union(x, y): x = find(x) y = find(y) if x < y: arr[y] = x else: arr[x] = y N, M = map(int, input().split()) arr = [i for i in range(N)] for i in range(M): a, b = map(int, input().split()) if find(a) == find(b): print(i+1) exit() union(a, b) p..

https://www.acmicpc.net/problem/2109 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 날짜보다 강의한 숫자가 더 크면 가장 싼 강연 포기 import sys input = sys.stdin.readline from heapq import heappop,heappush n=int(input()) arr=[list(map(int, input().split())) for _ in range(n)] arr.sort(key=lambda x: x[1]) h..

박스 순회하며 누적합. 자주나오는 유형이다. 중요한건 누적합은 뒤에서부터 쌓아줘야 중복이 안생긴다는것. 때문에 H부터 1까지 순회해주며 더해줬다. import sys input = sys.stdin.readline N, M, H = map(int, input().split()) boxes = [list(map(int, input().split())) for _ in range(N) ] dp = [0]*(H+1) for box in boxes: for idx in range(H,0,-1): if not dp[idx]: continue for num in box: if idx + num > H: continue dp[idx+num] += dp[idx] for num in box: dp[num] += 1 pr..

https://www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 배열돌리기 쓸데없이 귀찮지만 오늘 괜찮은 방법론을 배웠다. deque로 rotate시켜버리는 것. 따로 tmp를 안두어도 된다는게 너무 맘에 든다. import sys input = sys.stdin.readline from collections import deque def rotate_each(x,y,d,m): q = deque() for i in range(y-..

최소공배수 길이를 만들어 비교해줬다. 근데 다른 풀이보니까 그냥 상대 문자 길이만큼 곱해줘도 되더라..(꼭 최소가 아니라 그냥 공배수면됨) import sys input = sys.stdin.readline from math import gcd s = input().rstrip() t = input().rstrip() n = len(s) m = len(t) a = gcd(n,m) if s*(m//a) == t*(n//a): print(1) else: print(0)

https://www.acmicpc.net/problem/2026 2026번: 소풍 만약 K명의 친구 관계인 학생들이 존재하지 않는다면 -1을 출력한다. 그 외의 경우에는, K개의 줄에 학생들의 번호를 증가하는 순서로 한 줄에 한 개씩 출력한다. 여러 경우가 존재한다면 첫 번째 www.acmicpc.net K명 모두가 친구여야 통과하는 dfs를 짜주면 된다. import sys input = sys.stdin.readline def dfs(v,arr): if len(arr)==K: for num in arr: print(num) exit() for i in range(v+1,N+1): if not visited[i]: for num in arr: if num not in graph[i]: break el..