상상쓰

https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 오랜만에 올립니다. k 광년을 이동했을 때 다음에는 k-1, k, k+1 광년을 이동할 수 있다는 조건과 마지막은 1광년을 남겨야 하는 조건 때문에 최소한의 공간이동은 대칭적인 성격을 가질 수밖에 없다. 1 (1 * 1) 1 1 (2 * 1) 1 2 1 (2 * 2) 1 2 2 1 (3 * 2) 1 2 3 2 1 (3 * 3) 1 2 3 3 2 1 (4..

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net dp[k] = k원을 만들 수 있는 경우의 수 n번 돌 때마다 dp 배열은 갱신된다. (n번째는 n개의 수를 가지고 k원을 만들 수 있는 경우의 수) import sys n, k = map(int, sys.stdin.readline().split()) dp = [0] * (k+1) dp[0] = 1 for i in range(1, n+1): m = int(sys.stdin.readline()) fo..

https://www.acmicpc.net/problem/15989 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net 숫자 1 만으로 나타내는 방법은 각각 1가지가 있다. dp[i] = 1 다음 2 를 사용해도 된다고 하면 dp[2] = 2 이다. ((1, 1), (2)), dp[3] = 2 이다. ((1, 1, 1), (2, 1)) dp[4] 는 원래 (1, 1, 1, 1) 과 dp[4-2] 인 경우 (1, 1), (2) 에 2를 넣으면 되기 때문에..

https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 이렇게 또 하나를 배웠다. 위상 정렬로 조건(이미 정해진 순서)을 가지고 전체를 차례로 수행할 수 있는 경우를 구하는 방법이다. 문제는 위상 정렬이 가능한 경우만 주어지므로 사이클 등의 경우는 무시했다. 또한, 조건에 맞는 답은 여러 가지일 수 있다. 자신의 앞에 학생이 없는 경우(node[i] = 0)인 경우는 가장 먼저 올 수 있다. 이 학생들을 qu..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 출발 도시와 도착 도시가 같은 버스가 있을 수 있다는 생각을 처음에 못 했다. 그래서 코드를 추가했고 비용이 0인 버스가 있어서 fee = {} 비어있을 때랑 값이 있을 때 나눠서 다익스트라 알고리즘으로 풀었다. import sys from collections import defaultdict, deque N = int(sys.stdin.readline()) M..

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 받은 배열을 순서대로 이동하면서 합을 구한 뒤 그 합이 S 를 넘으면 k = 0 을 시작으로 1씩 더해주면서 temp 가 S 보다 작아질 때까지 array[k] 를 빼준다. 이때 연속된 수들의 부분합이 S 를 넘어가는 길이는 i - k + 2 이며 그 중 최솟값을 반환하면 된다. import sys N, S = map(int, sys.stdin.readline().split()) a..

https://programmers.co.kr/learn/courses/30/lessons/42885?language=python3 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 최대 2명씩밖에 탈 수가 없으므로 가장 무거운 사람을 기준으로 2명을 태워 보낼 수 있는지 없는지를 판단한다. 오름차순으로 정렬된 people 에서 end -= 1 을 해주면서 2명을 태워 보낼 수 있으면 start += 1 시켜준다. start 가 end 를 넘어갈 때 answer 을 반환해주면 된다. ..

https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 플러그를 빼야 하는 상황이 생기면 꽂은 플러그 중 더 이상 사용하지 않거나 사용한다면, 가장 나중에 사용될 플러그를 뽑으면 된다. N = 2, K = 7 이고, plug = [2, 3, 2, 3, 1, 2, 7] 를 예로 들면, usage = {2: deque([0, 2, 5]), 3: deque([1, 3]), 1: deque([4]), 7: deque([6])}) 를 만들어 해당 전기용품을 키..

https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net combinations 을 직접 구현해보았고 구한 candidate 배열과 words 배열의 단어랑 비교하여 읽을 수 있는 단어를 찾는 것을 빠르게 구하는 게 중요했다. 우선, 'a', 'c', 'i', 'n', 't' 는 모든 단어마다 있으므로 K - 5 가 음수면 0을 출력해야 하며, K 가 26이면 모든 N개의 단어를 읽을 수 있으므로 N을 출력해주면 된다. dictionary 를 이..

https://www.acmicpc.net/problem/2460 2460번: 지능형 기차 2 최근에 개발된 지능형 기차가 1번역(출발역)부터 10번역(종착역)까지 10개의 정차역이 있는 노선에서 운행되고 있다. 이 기차에는 타거나 내리는 사람 수를 자동으로 인식할 수 있는 장치가 있다. www.acmicpc.net 칙칙폭폭 import sys n = 0 answer = 0 for i in range(10): IN, OUT = map(int, sys.stdin.readline().split()) n += (OUT - IN) answer = max(answer, n) print(answer)