https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 전형적인 위상정렬 문제이다. 다만 마지막 도착점에 대한 것이 아니라, 중간의 목표 지점에만 도달하면 되는 것이기 때문에 약간의 greedy를 포함하면 편하다. => max_times 배열 이용! import sys from collections import deque input = sys.stdin.readline t = int(input().rstrip()) for _ in range(t)..

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 전형적인 투포인터 유형이다. 그동안 투포인터를 양 쪽에서 만나는 방식으로 사용했는데, 같이 출발하는 방식도 있다! import sys input = sys.stdin.readline n,s = map(int,input().rstrip().split()) numbers = list(map(int,input().rstrip().split())) prefix_sum = [0 for _ i..

https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 해당 index까지 왼쪽에서는 높이가 몇인 벽이 가장 높은지, 오른쪽에서는 높이가 몇인 벽이 가장 높은지를 저장해놓은 후, 양쪽 벽 중 낮은 벽까지만 물이 찬다는 아이디어를 사용하면 된다. import sys input = sys.stdin.readline h,w = map(int,input().rstrip().split()) left = [0] * w right = [0] * ..

https://www.acmicpc.net/problem/22860 22860번: 폴더 정리 (small) main 폴더 하위에는 FolderA 폴더 하위에 있는 File1, File2, FolderB 폴더 하위에 있는 File1, File3이 있다. 파일의 종류는 File1, File2, File3 총 3가지이고, 파일의 총 개수는 File1, File2, File1, File3 총 4개이다. mai www.acmicpc.net 아이디어 최근 본 코딩테스트에서 거의 똑같은 문제가 나왔었다. 근데 또 문제 잘못 읽음...ㅎㅎ 출력 순서를 반대로 했었다. 위상정렬 아이디어를 사용했다. folder_dict에서 각 key에 해당하는 value는 길이가 3인 리스트로 구성되어있다. 0번 인덱스는 해당 폴더의 ..

https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 아이디어 전형적인 위상정렬 문제이다. import sys from collections import deque input = sys.stdin.readline n,m = map(int,input().rstrip().split()) routes = [0] * (n+1) graph = [[] for _ in range(n+1)] for _ in range(m): a,b = map(int,input().rstrip().split..

https://www.acmicpc.net/problem/1548 1548번: 부분 삼각 수열 세 수 x, y, z가 x+y>z, x+z>y, y+z>x의 관계를 만족하면, 세 수는 삼각관계에 있다고 한다. 마찬가지로 길이가 N인 수열 B(b[0], b[1], ..., b[n-1])의 모든 b[i], b[j], b[k]가 삼각관계에 있으면 이 수열은 삼각 www.acmicpc.net 아이디어 해당 링크 참고함 https://isukorea.com/group/morgorithm/board/b/8 import sys import heapq input = sys.stdin.readline n = int(input().rstrip()) A = list(map(int, input().rstrip().split()..