https://www.acmicpc.net/problem/18352 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 문제 풀이: BFS를 사용해서 그래프를 탐색하면서 최단 거리를 dist[] 배열에 저장하였고, 탐색이 끝난 후에 dist 배열을 돌면서 값이 K인 경우를 출력하였다. K인 경우가 없을 때는 -1을 출력하였다. import sys from collections import deque N, M, K, X = map(int, sy..
복습
www.acmicpc.net/problem/19621 19621번: 회의실 배정 2 서준이는 아빠로부터 N개의 회의와 하나의 회의실을 선물로 받았다. 각 회의는 시작 시간, 끝나는 시간, 회의 인원이 주어지고 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없다. 단, www.acmicpc.net 임의의 회의 K(1≤ K ≤ N)는 회의 K − 1과 회의 K + 1과는 회의 시간이 겹치고 다른 회의들과는 회의 시간이 겹치지 않는다. 이 조건 때문에 dfs로 구현하여 풀 수 있다. K번째 회의를 선택하고 K+2번째 회의를 선택하는 경우와 K번째 회의를 선택하지 않고 K+1번째 회의를 선택하는 경우 import sys sys.setrecursionlimit(10**9) N = int(sys.stdin...
www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제풀이: dp를 어떻게 짜야 할 지 생각해내는 것이 어려웠다. 최솟값을 더하는 방법으로 하자니 동일한 비용이 나오는 경우를 고려하는 것이 어려웠고.. 그래서 각각의 경우를 모두 구하는 것이구나 하는 걸 깨달았다..(사실 힌트를 좀 받았다..) 그걸 깨닫고 나니 푸는 것은 간단했다. import sys N = int(sys.stdin.readline()) cost = [] for _ in ..
www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 문제풀이: 모든 경우를 탐색해야 하므로 DFS를 이용하여 풀 수 있다. 연산자를 주어진 배열의 형태로 접근해 보려고 하다가.. 어차피 위치는 정해져 있으니까 개수만 가져와서 함수를 만들었다. DFS 구현 부분에서 elif라고 적었다가 오류가 났었다.. 간단하게 풀 수 있는 문제인데 너무 어렵게 생각했던 것 같다. import sys input = sys.s..
www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 문제풀이: DP를 이용해서.. 1부터 N까지 숫자의 최소 표현 개수를 모두 구한다. 구하는 방법을 생각해내는 게 어려웠는데, dp[0]=0, dp[1]=1 이라는 초기값을 넣어주고 2~N까지 i를 돌면서 i에서 i보다 같거나 작은 제곱 수를 하나씩 빼면서 최솟값을 갱신하는 방식으로 풀었다. 그래서 제곱 수의 배열인 arr도 따로 만들었고, 제곱한 값이 N보다 같거나 작은 경우..
www.acmicpc.net/problem/10448 10448번: 유레카 이론 프로그램은 표준입력을 사용한다. 테스트케이스의 개수는 입력의 첫 번째 줄에 주어진다. 각 테스트케이스는 한 줄에 자연수 K (3 ≤ K ≤ 1,000)가 하나씩 포함되어있는 T개의 라인으로 구성되어 www.acmicpc.net 아이디어: 3
www.acmicpc.net/problem/20302 20302번: 민트 초코 상원이가 고른 디저트가 “민트 초코”인 경우 mint chocolate, “치약”인 경우 toothpaste를 출력한다. www.acmicpc.net 아이디어: 문제에 어떻게 접근해야하는지 도무지 모르겠다. 단순하게 풀면 풀리지 않을 거라는 건 자명하고, 소인수분해를 이용하여 풀어야 하는 것 같은데 정수와 정수가 아닌 유리수를 소인수분해를 이용해서 어떻게 알 수 있을까? 분모와 분자를 각각 소인수분해해서 나눴을때 분모에 소수가 남으면 정수가 아니다.. 곱셈 뒤에 있는 수는 분자, 나눗셈 뒤는 분모.. 각 수를 소인수분해하고 분자인 경우에는 해당하는 소수를 +1로 카운트, 분모인 경우에는 -1로 카운트한다. 그리고 카운트 배열을..
www.acmicpc.net/problem/16563 16563번: 어려운 소인수분해 첫째 줄에는 자연수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 자연수 ki (2 ≤ ki ≤ 5,000,000, 1 ≤ i ≤ N)가 N개 주어진다. www.acmicpc.net 아이디어: 소수판정법을 이용하여 2부터 루트n 까지 for문을 돌면서 나누어지는 수를 출력하고 계속 반복하는 방식으로 구현했더니 시간초과가 났다. #시간초과 import sys, math N = int(sys.stdin.readline()) k = list(map(int, sys.stdin.readline().split())) def solve(n): m = math.floor(n**0.5+1) for i in ra..
www.acmicpc.net/problem/14490 14490번: 백대열 n과 m이 :을 사이에 두고 주어진다. (1
www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 아이디어: 플로이드 문제에 조건을 추가했다. 경로도 같이 출력하라고 한다... 쉽게 봤다가 정말 토할 뻔 했다.. ㅎㅎ.. 처음에는 단순히 최솟값을 갱신하면서 k를 저장하면 될 것이라 생각했지만.. k만 저장해서는 안됐다. i-k-j의 경로이더라도 i-k 사이 혹은 k-j 사이에 또 다른 최단 경로가 존재할 수 있기 때문이다. 따라서 이걸 어떻게 하나 참 오래 생각하다가 계속 i-k사이의, k-j사이의 경로..
