Python/Coding Test

21277 짠돌이 호석

문제 https://www.acmicpc.net/problem/21277 21277번: 짠돌이 호석 DIY(Do It Yourself)는 호석이가 제일 좋아하는 컨텐츠이다. 이번 DIY는 동네 친구 하늘이랑 각자 직소 퍼즐을 하나씩 맞춰보기로 했다. 두 개의 퍼즐은 각자 N1 행 M1 열과 N2 행 M2 열의 격자 형태 www.acmicpc.net 접근 카카오 기출 문제 중 자물쇠와 열쇠 문제에서 힌트를 얻어, 기준 퍼즐1의 범위를 확장 시켜서 전체 경우마다 퍼즐2와 맞춰보는 식으로 풀이했다. 퍼즐의 크기 제한이 50 이므로 상하좌우 50씩 확장할 경우, 최대로 확장될 수 있는 퍼즐의 한 변의 길이는 150이다. 따라서 회전까지 고려했을 때 최대 4 * 100 * 100 * 50 * 50 = 10 * 9..

10703 유성

문제 https://www.acmicpc.net/problem/10703 10703번: 유성 작고 특이한 모양의 유성 사진이 인터넷에 올라왔다. 사진에는 매우 높은 곳에서 떨어지고 있는 유성이 허공에 찍혀 있었다. 유성이 떨어지고 난 뒤의 사진도 있었지만 안타깝게도 소실돼버려 www.acmicpc.net 접근 각각의 유성 조각에 대해 떨어질 수 있는 높이의 최솟값을 구한 후, 모든 유성에 대해 구한 최솟값 만큼 아래로 떨어트린다. 아래와 같이 유성 조각 아래에 땅이 있고 또 그 아래에 유성 조각이 있는 경우 또한 처리해줘야 한다. . . . . . . . . . . . X X X X . . . . . X . . . . . . . . X # # # # # # . . X . . . . . # . . X X ..

13168 내일로 여행

문제 https://www.acmicpc.net/problem/13168 13168번: 내일로 여행 첫 번째 줄에는 한국에 있는 도시의 수 N(1 ≤ N ≤ 100)과 1인당 내일로 티켓의 가격 R(1 ≤ R ≤ 1,000,000)이 주어집니다. 두 번째 줄에는 N개의 도시의 이름이 주어집니다. 도시의 이름은 알파벳 대소 www.acmicpc.net 접근 문제를 처음 보고 내일로 티켓을 구입했을 때와 구입하지 않았을 때의 비용 정보를 따로 저장하고, 동일한 최단거리 알고리즘으로 비용을 계산한 후 비교해야 겠다고 생각했다. 경로마다 비용이 다르므로 다익스트라와 플로이드 워셜 중 하나를 이용하기로 했다. 문제에서 방문하려는 곳의 전체 경로가 정해져 있고 각 부분 경로마다 최단거리로 이동해서 목적지까지 드는 ..

1421 나무꾼 이다솜

문제 https://www.acmicpc.net/problem/1421 1421번: 나무꾼 이다솜 첫째 줄에 이다솜이 가지고 있는 나무의 개수 N과 나무를 자를 때 드는 비용 C와 나무 한 단위의 가격 W이 주어진다. 둘째 줄부터 총 N개의 줄에 이다솜이 가지고 잇는 나무의 길이가 한 줄에 하나 www.acmicpc.net 접근 나무의 개수가 50보다 작고 자를 수 있는 나무 길이가 10000보다 작으므로, 자를 수 있는 모든 길이에 대해 벌 수 있는 돈을 계산해서 최댓값을 구했다. 주의할 점은 가지고 있는 나무를 전부 잘라서 팔아야하는 것은 아니므로, 해당 나무를 팔았을 때 얻는 비용과 자를 때 드는 비용의 차가 양수일때만 나무를 판다. 풀이 n, c, w = map(int, input().split(..

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 접근 문제를 봤을 때 우선 대강 정렬하고 스위핑해서 풀어야겠다고 생각했다. 까다로운 부분이 원형으로 이루어진 버스 노선 처리인데, 카카오 기출 문제 중 원을 두 배 늘려서 직선으로 처리했던게 떠올라서 직선으로 바꾸어 처리했다. 첫 번째 시도에서는 시간초과가 났는데 삭제할 노선을 저장할 때 배열 대신 딕셔너리를 사용했고, 이미 정렬된 상태이기 때문에 ..