생각 생각

https://acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net dp 문제. import sys input=sys.stdin.readline N=int(input()) dp=[0]*(N+1) for i in range(1,N+1): t,v=map(int,input().split()) dp[i] = max(dp[i], dp[i - 1]) # 어제까지 번 돈만큼은 최소 벌 수 있음 if i+t-1>N: continue dp[t+i-1]=ma..

https://acmicpc.net/problem/24463 24463번: 미로 첫 번째 줄에는 미로의 크기 $N, M$이 주어진다. $(3 \le N, M \le 2,001$, $N, M$은 홀수$)$ 두 번째 줄부터는 미로의 정보가 주어진다. 두 번째 줄부터 $N$줄에 거쳐 각 줄에는 길이가 $M$이고 .과 +만으로 이 www.acmicpc.net dfs에 익숙치 않아 까다로웠던 문제. 핵심은 '같은 지점으로 돌아오는 길이 존재하지 않고' 였다. 다시 말해 길은 하나이니 마치 bfs처럼 써놨지만 dfs로 푸는 게 맞다고 생각한다. import sys sys.setrecursionlimit(10**9) input=sys.stdin.readline N,M=map(int,input().split()) se..

https://acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net bfs를 두 번 돌려서 탈출할 수 있을지를 고려해보는 특이한 문제였다. import sys from collections import deque input=sys.stdin.readline # 불이 몇 시에 해당 위치에 퍼질 지를 기록할 것이다. dy=[1,-1,0,0] dx=[0,0,1,-1] C,R=map(int,input().split()) graph=[] fires=deque() ..

https://acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 한 문제로 참 야무지게도 먹었다. 맛있다. 총 세 가지 방법으로 풀었다. 풀이 1. 다익스트라 가장 직관적으로 떠오른 풀이법. 그런 풀이가 으레 그렇듯, 가장 오래 걸리더라. 발상은 어렵지 않다. 중량 제한이 가장 큰 순서대로 정렬시킨 후, 최대 힙에 넣어 가장 큰 중량으로 끝점에 도달하는 경우를 찾는다. 시작과 끝 점이 있을 때 다익스트라를 쓸..

https://acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 유니온 파인드에 대해 공부했다. 경로 압축을 한 버전으로 풀었다. 방법 1. 유니온 파인드 # Union과 find로 disjoint set을 찾아내는 알고리즘이어서 union-find이다. import sys input=sys.stdin.readline N,M=int(input()),int(input()) parent=[i for i in range(N+1)] # 이 find 함수는 경로 압축이 이루어..

https://acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 중복조합이라는 사실이 생각이 안 나서 한참을 고민한 문제. 이 문제는 결국 N개의 동일한 의자를 K-1개의 칸막이로 나누는 것이라 보아도 된다. N,K=map(int,input().split()) dp=[[0]*(i+1) for i in range(N+K)] div=1000000000 for i in range(1,N+K): dp[i][0]=1 for j in range(1,i): dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])%div # 파스칼의 삼각형 구현 dp[i][i]=1 print(dp[N+K-1][K-1]..

https://acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 그리디가 어렵다는 걸 본격적으로 알게 된 문제. 자력으로는 못 풀고 여기저기 참고해서 겨우 이해했다. import sys input=sys.stdin.readline N,C=map(int,input().split()) M=int(input()) houses=[0]*M truck,w,ans=[],0,0 for i in range(M): houses[i]=list(map(int,input..

https://acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 깔끔한 1트클 2중 bfs. 속도도 준수했다. import sys from collections import deque input=sys.stdin.readline N=int(input()) answer=N*2-1 # 왼쪽 끝 1*1섬에서 오른쪽 끝 1*1 섬까지 간다 칠 때 최대 거리 graph=[list(map(int,input().split())) for _ in range(N)] visited=[[0]..