Coding Test

[1325] 효율적인 해킹(BFS)

1325번: 효율적인 해킹첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한www.acmicpc.net import sysfrom collections import dequeinput = sys.stdin.readline# 컴퓨터개수, 신례관계개수n,m,=map(int, input().split())# 인접 리스트graph=[[] for _ in range(n+1)]# 정답리스트answer=[0]*(n+1)def bfs(v): queue = deque() queue.append(v) visited[v]=True whi..

[18352] 특정 거리의 도시 찾기(다익스트라・heapq, BFS・deque)

18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 다익스트라 from heapq import heappush, heappop import sys input = sys.stdin.readline # 도시, 거리, 거리정보, 출발노드 n,m,k,x = map(int, input().split()) # 최단거리 리스트 d = [sys.maxsize] * (n+1) # 인접 리스트 graph = [[] for _ in range(n+1)] for ..

[2342] Dance Dance Revolution(3차원 DP)

2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 분석 D[N][L][R] : N개의 수열을 수행한 후 왼발의 위치가 L, 오른발의 위치가 R일 때 최소 누적 힘 mp[i][j] : i에서 j로 이동하는데 드는 힘 오른발 : D[N][L][R] = min(D[N-1][L][i] + mp[i][R]) 왼발 : D[N][L][R] = min(D[N-1][i][R] + mp[i][L]) 풀이 import sys input=sys.stdin.readline # N개의 열, L 왼발, ..

[1328번] 고층 빌딩 (빌딩 순서 구하기, 3차원 DP)

1328번: 고층 빌딩 상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼 www.acmicpc.net 분석 D[N][L][R] : N개의 빌딩이 있고 왼쪽에서 볼 때 L개, 오른쪽에서 볼 때 R개가 가능한 경우의 수 가장 작은 빌딩을 N번째로 배치한다고 가정 가장 앞에 배치 : D[N][L][R] = D[N-1][L-1][R] ← 왼쪽에서 보이는 갯수가 +1 가장 뒤에 배치 : D[N][L][R] = D[N-1][L][R-1] ← 왼쪽에서 보이는 갯수가 +1 가운데에 배치 : D[N][L][R] = D[N-1][L][R] * (N-2) ← 보이는 갯수 동일, 가..

[1915번] 가장 큰 정사각형

1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 1로 된 가장 큰 정사각형의 크기 출력 0 1 0 0 0 1 1 1 1 1 1 0 0 0 1 0 import sys input=sys.stdin.readline n,m=list(map(int, input().split())) d=[[0 for j in range(1001)] for i in range(1001)] max=0 # 변의 길이 for i in range(0,n): # 세로 arr=list(input()) for j in range(0,m): # 가로 d[i][j]=int(arr[j]) if d[i][j]==1 and j>..

[13398번] 연속합2 (한개 수 삭제)

13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 분석 L[N] : 왼쪽에서부터 N을 포함한 최대 연속 합 L[i]= max(A[i], L[i-1]+A[i]) R[N] : 오른쪽에서부터 N을 포함한 최대 연속 합 R[i]= max(A[i], R[i+1]+A[i]) L[N-1] + R[N+1] : N을 1개 제거한 최댓값 (1개의 수를 삭제할 수 있기 때문) [1912번] 연속합 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 ..

[1912번] 연속합

1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 n = int(input()) list = list(map(int, input().split())) dp = [0] * n # 최대 연속합 dp[0] = list[0] for i in range(1, n): dp[i] = max(list[i], dp[i-1]+list[i]) # list[i] / 이전최대연속합 + list[i] # print(dp) print(max(dp))

[10844번] 쉬운 계단 수(2차원 DP)

10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 분석 D[N][H] : 길이가 N인 계단에서 H높이로 종료되는 계단 수를 만들 수 있는 경우의 수 D[i][0] : 0인 경우, 뒤에 1만 올 수 있음 ➔ D[i][1] D[i][j] : 1~8인 경우, -1, +1 높이 올 수 있음 ➔ dp[i][j]= dp[i-1][j-1] + dp[i-1][j+1] D[i][9] : 9인 경우, 뒤에 8만 올 수 있음 ➔ D[i][8] 풀이 import sys input=sys.stdin.readline # 길이 n=int(input()) # dp[계단길이][계단높이] dp=[[0 for j in range(11)] for i in ran..

[11726번] 2×n 타일링

11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 분석 D[N] : 길이 N으로 만들 수 있는 타일의 경우의 수 D[N-1] : n-1까지 타일이 채워져있는 경우 ➔ 새로운 타일 1개를 채워 N길이를 만듦 D[N-2] : n-2까지 타일이 채워져있는 경우 ➔가로로 타일 2개를 래워 N길이를 만듦 D[N] = D[N-1]+D[N-2] 풀이 # 2*n크기 직사각형을 2*1/1*n으로 채우는 방법의 수 n = int(input()) d=[0]*1001 # n의 최댓값 1000 d[1]=1 d[2]=2 for i in range(3, n+1..

[14501번] 퇴사

14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net bottom up n = int(input()) s = [list(map(int, input().split())) for i in range(n)] dp = [0 for _ in range(n+1)] for i in range(n): for j in range(i+s[i][0], n+1): if dp[j] < dp[i] + s[i][1]: dp[j] = dp[i] + s[i][1] print(dp[-1]) top down n = int(input()) dp = [0]*(n+2) # 오늘부터 퇴사일까지 벌수있는 최대수입 (점화식 테이블) t=[0]*(n+1) # 상담에 필요한 일수 p=[0]*(n+1)..