상상쓰

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://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)

https://www.acmicpc.net/problem/2501 2501번: 약수 구하기 첫째 줄에 N과 K가 빈칸을 사이에 두고 주어진다. N은 1 이상 10,000 이하이다. K는 1 이상 N 이하이다. www.acmicpc.net K번째 약수 구하기! import sys N, K = map(int, sys.stdin.readline().split()) for i in range(1, N+1): if N % i == 0: K -= 1 if K == 0: print(i) break else: print(0)

https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 쉽게 생각했을 때, 해당 열에 고인 빗물의 양은 해당 열을 기준으로 왼쪽에서 가장 높은 블록과 오른쪽에서 가장 높은 블록 중 가장 작은 길이 - 해당 열의 블록의 길이이다. (단, >= 0) leftMaxRainwater[i] = 0 ~ i열로 이동할 때 가장 긴 블록의 길이 rightMaxRainwater[i] = W-1 ~ i열로 이동할 때 가장 긴 블록의 길이 를 구한 뒤 ..

https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 입력 문자열 string 에 strip() 함수 없이 받으면 '틀렸습니다' 을 받는다. 예로 '(()[[]])([])' 를 구해보자. 분배법칙과 스택을 이용한다. 즉, '(())' + '([[]])' + '([])' '(' : temp = 2 '((' : temp = 2 * 2 = 4 '(()' : 바로 이전에 여는 괄호가 들어왔고 '()' 로 괄호가 닫혔으므로 temp = 4 를 answer ..

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net DFS 알고리즘을 이용하여 모든 경우를 구하여 최댓값과 최솟값을 반환하면 된다. 연산자의 개수는 len(A) - 1 이기 때문에 rf() 의 인자 i 가 len(A) 일 때 하나의 계산이 끝나므로 그때의 값을 비교하면 된다. o[] 로 해당 연산을 할 수 있는지 알 수 있다. rf() 가 시작할 때 해당 연산자를 썼다는 의미로 -1을 해주고 ..

https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net union-find 알고리즘을 사용하여 분리 집합을 표현하였다. 예를 들어, {1, 2, 3}, {4, 5} 인 집합에서 '0 3 5' 의 입력을 받으면 root[1] = 5, root[2] = 5, root[3] = 5, root[4] = 5, root[5] = 5로 하여 root[i] = 5가 나오는 i는 같은 집합의 원소라고 할 수 있다. 5가 아닌 ..

https://www.acmicpc.net/problem/10250 10250번: ACM 호텔 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T 개의 테스트 데이터로 이루어져 있는데 T 는 입력의 맨 첫 줄에 주어진다. 각 테스트 데이터는 한 행으로서 H, W, N, 세 정수 www.acmicpc.net 각 층의 방의 개수가 같으므로 W 는 무시해도 된다. divmod 를 이용하여 몫과 나머지로 방 번호를 구할 수 있다. 나머지가 0이 될 때만 주의해주면 된다. import sys T = int(sys.stdin.readline()) for i in range(T): H, W, N = map(int, sys.stdin.readline().split()) q, r = divmod(N, ..