Python

2563 전깃줄

문제 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 접근 전깃줄이 교차하지 않으려면 첫 번째 전봇대의 원소 x, y에 대해 x < y인 경우 연결된 두 번째 전봇대의 원소 f(x), f(y)가 f(x) < f(y)를 만족해야 한다. (f는 문제에서 주어진 연결 정보) 따라서 한 전봇대를 기준으로 정렬한 뒤, 다른 전봇대에서 만들 수 있는 가장 긴 오름차순 수열의 길이를 구하면 되므로 LIS를 이용하기로 했다. 풀이 n = int(input()) a ..

15728 에리 - 카드

문제 https://www.acmicpc.net/problem/15728 15728번: 에리 - 카드 첫째 줄에 N, K(0 ≤ K < N ≤ 100)가 주어지고 둘째 줄에는 N개의 ‘공유 숫자카드’에 적혀 있는 정수, 셋째 줄에는 N개의 ‘팀 숫자카드’에 적혀 있는 정수가 주어진다. 이 수는 -10,000보다 크거나 www.acmicpc.net 접근 문제에 주어진 n의 범위가 크지 않으므로, 얻을 수 있는 점수들을 전부 계산해서 k개를 제외한 뒤 남아있는 카드로 만들 수 있는 값 중 최대값을 출력했다. 풀이 계산한 모든 점수를 가지고 있는 배열을 정렬해서 큰 순서대로 k개를 제하는데, 이미 전에 제거된 카드인지 확인하기 위해 Counter를 이용했다. 또한 k개를 제한 후, 배열에 남아있는 가장 큰 값..

16933 벽 부수고 이동하기 3

문제 https://www.acmicpc.net/problem/16933 16933번: 벽 부수고 이동하기 3 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 풀이 from collections import deque import sys input = sys.stdin.readline dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] n, m, k = map(int, input().split()) board = [input().rstrip() for _ in range(n)] check = [[..

9996 한국이 그리울 땐 서버에 접속하지

문제 https://www.acmicpc.net/problem/9996 9996번: 한국이 그리울 땐 서버에 접속하지 총 N개의 줄에 걸쳐서, 입력으로 주어진 i번째 파일 이름이 패턴과 일치하면 "DA", 일치하지 않으면 "NE"를 출력한다. 참고로, "DA"는 크로아티어어로 "YES"를, "NE"는 "NO"를 의미한다. www.acmicpc.net 접근 정규식 사용 풀이 import re n = int(input()) s = input() idx = s.index("*") pattern = s[:idx] + "[a-z]*" + s[idx + 1:] p = re.compile(pattern) for _ in range(n): t = input() if p.fullmatch(t): print("DA") e..

10165 버스 노선

문제 https://www.acmicpc.net/problem/10165 10165번: 버스 노선 첫 번째 줄에는 버스 정류소의 개수 N(3 ≤ N ≤ 1,000,000,000)이 주어지고 두 번째 줄에는 버스 노선의 수 M(2 ≤ M ≤ 500,000)이 주어진다. 각 버스 노선은 1부터 M까지의 번호로 구분된다. 그 다음 M개 www.acmicpc.net 접근 문제를 봤을 때 우선 대강 정렬하고 스위핑해서 풀어야겠다고 생각했다. 까다로운 부분이 원형으로 이루어진 버스 노선 처리인데, 카카오 기출 문제 중 원을 두 배 늘려서 직선으로 처리했던게 떠올라서 직선으로 바꾸어 처리했다. 첫 번째 시도에서는 시간초과가 났는데 삭제할 노선을 저장할 때 배열 대신 딕셔너리를 사용했고, 이미 정렬된 상태이기 때문에 ..

2749 피보나치 수 3

문제 https://www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 접근 문제에서 주어지는 N의 범위가 매우 크기 때문에, 피보나치 수들에 어떠한 주기가 있을 것으로 판단하고 구글 검색 후 피사노 주기라는 개념을 알게 되었다. 피사노 주기 def) In number theory, the nth Pisano period, written as π(n), is the period with which the sequence of Fibonacci numbers taken modulo n repeats. 즉, 주기를 p라고 했을 때, n번째 피보나..

21939 문제 추천 시스템 Version 1

문제 https://www.acmicpc.net/problem/21939 21939번: 문제 추천 시스템 Version 1 tony9402는 최근 깃헙에 코딩테스트 대비 문제를 직접 뽑아서 "문제 번호, 난이도"로 정리해놨다. 깃헙을 이용하여 공부하시는 분들을 위해 새로운 기능을 추가해보려고 한다. 만들려고 하는 명령 www.acmicpc.net 접근 처음 생각한 방법은 딕셔너리에 난이도별로 문제를 저장하려 했으나, 난이도별로 관리할 필요가 없다는 생각이 들어서 우선순위큐로 바꿨다. 가장 어려운 문제와 가장 쉬운 문제를 추천해야 하므로 우선순위큐 2개를 사용했고, 푼 문제들을 저장하기 위해 딕셔너리를 사용했다. solve 연산을 수행할 때마다 저장된 문제를 갱신하는 방법으로 풀었으나 시간초과가 발생해서 ..

13334 철로

문제 https://www.acmicpc.net/problem/13334 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 접근 가장 처음 시도한 방법은 정렬과 스위핑을 사용해서 철도의 구간과 구간에 들어가는 경로의 개수를 갱신해나가는 방법으로 풀이했으나 틀림 -> 반례가 무엇인지 못찾겠다... 다른 방법으로 정렬된 전체 경로들(시작점과 끝점이 철도의 길이 d보다 작거나 같은 경로들)에 대해, 철도의 길이 d에 함께 포함될 수 있는 경로들을 따로 저장(q)해놓고..

2485 가로수

문제 https://www.acmicpc.net/problem/2485 2485번: 가로수 첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가 www.acmicpc.net 접근 모든 가로수의 간격이 같으려면 주어진 가로수의 간격의 최대공약수를 구해야 한다고 생각해서 유클리드 호제법을 이용했다. 각 간격을 저장하고 저장된 모든 간격에 대한 최대공약수를 계산한 후, 각 간격을 최대공약수로 나눈 몫 - 1을 합해서 정답을 구한다. 풀이 def gcd(x, y): if x % y == 0: return y return gcd(y, x % y) n = int(i..