Total

[2251] 물의 양 구하기 (물통, BFS)

2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 분석 (BFS 과정) 1. 노드에서 갈 수 있는 6개의 경우(A→B, A→C, B→A, B→C, C→A, C→B)에 관해 다음 노드로 정해 큐에 추가 A,B,C 무게가 동일한 노드에 방문한 이력이 있을 때는 큐에 추가하지 않음 2. 보내는 물통의 모든 용량을 받는 물통에 저장하고, 보내는 물통에는 0을 저장 단, 받는 물통이 넘칠 때는 초과하는 값만큼 보내는 물통에 남김 3. 큐에 추가하는 시점에 1번째 물통(A)의 무게가 0일 때가 있으면 ..

[1707] 이분 그래프(DFS)

1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 이분그래프 각 집합에 속한 노드끼리 서로 인접하지 않는 두 집합으로 그래프의 노드를 나눌 수 있을 때 분석 싸이클이 발생하지 않으면 탐색을 하면서 다음 노드를 이번 노드와 다른 집합으로 지정 기존의 탐색 메커니즘에서 탐색한 노드에 다시 접근하게 됐을 때 현재 노드의 집합과 같으면 이분 그래프가 불가능 DFS를 실행할 때 현재 노드에서 연결된 노드 중 이미 방문한 노드가 나와 같은 집합이면 이분그래프가 아닌것으로 판별 실행 결과가 이분그래프가 아니면 이후 노드는 ..

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