문제 주소 https://www.acmicpc.net/problem/14658 14658번: 하늘에서 별똥별이 빗발친다 첫째 줄에 네 정수 N, M, L, K가 주어진다. (1 ≤ N, M ≤ 500,000, 1 ≤ L ≤ 100,000, 1 ≤ K ≤ 100) N은 별똥별이 떨어지는 구역의 가로길이, M은 세로길이, L은 트램펄린의 한 변의 길이, K는 별똥별의 수를 www.acmicpc.net 문제 해석 문제 풀이 단순히 n, m을 통해 그려서 풀기에는 너무 큰 입력 범위이다. 따라서 모든 범위를 완전 탐색해서 구할 수는 없다. 떨어지는 별똥별의 입력 범위는 1
문제 주소: https://www.acmicpc.net/problem/30023 30023번: 전구 상태 바꾸기 $N$개의 전구가 일렬로 세워져 빛나고 있다. 각각의 전구는 빨간색, 초록색, 파란색 중 하나의 색으로 빛나고 있다. 지원이는 $N$개의 전구 중 연속한 세 전구를 선택한 후에 그 전구들의 상태를 www.acmicpc.net 문제 해석 문제 풀이 전구를 시작 색의 경우의 수는 3가지이다. 0122의 전구가 존재한다면 1. 012 2. 120 3. 201 다음의 경우의 수를 시작으로 0번째 전구와 동일하도록 끝까지 전구의 상태를 변경하여, 조건에 맞는다면 최솟값을 갱신해나간다. 문제 코드 import sys input = sys.stdin.readline # input n = int(input(..
문제 주소: https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 문제 해석 문제 풀이 이 문제가 다익스트라 문제라는 것을 알았다면, 최소 경로를 지나갈 때 목적지 후보들 중에서 G H의 경로를 지나는 경우가 최소가 되는 목적지를 구해야 한다는 것을 알 수 있다. 이 조건을 해결하기 위해서 크게 두 가지 방법을 사용할 수 있다. 정석적인 방법과 애드혹스러운 기교를 통해 문제를 해결하는 방법이 존재한다. 내가 푼 방법은 후자의 방법이지만 먼저 정..
문제 주소: https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 문제 해석 문제 풀이 문제 설명에 애매한 부분이 존재해서 좀 애먹었다. 먼저 컨테이너 벨트는 위 아래로 존재한다. 시계 방향으로 회전하며, N의 위치에 도달하면 N+1로 2N의 위치에 도달하면 1의 위치로 시계 방향으로 회전한다. -> 이 부분을 보자마자 deque를 떠올려 구현했다. 1번 칸은 "올리는 위치" 이며, N번 칸은 "내리는 위치" 이다. 내리는 위치..
대회 주소 https://codeforces.com/contest/1807 Dashboard - Codeforces Round 859 (Div. 4) - Codeforces codeforces.com 문제 풀이 A번 a + b = c 또는 a - b = c 수식을 사용한 결과 a, b, c가 주어진다. a, b, c를 통해 연산자의 부호가 +, - 인지 출력하는 문제 import sys input = sys.stdin.readline # input t = int(input()) for _ in range(t): a, b, c = map(int, input().split()) if a - b == c: print("-") else: print('+') a - b == c 를 만족하는지, 안하는지 확인 후 ..
대회 주소 https://codeforces.com/contest/1802 Dashboard - Codeforces Round 857 (Div. 2) - Codeforces codeforces.com 문제 풀이 A번 좋아요와 좋아요 취소를 따로 구해 규칙에 맞게 정답을 구하면 된다. B번 성별이 확정된 돼지, 미확정 돼지, 확정된 우리로 경우의 수를 나누고, 조건에 따라 우리의 개수를 구하면 된다. C번은 너무 복잡해 문제를 보고 넘겼다..
대회 주소 https://codeforces.com/contest/1800 Dashboard - Codeforces Round #855 (Div. 3) - Codeforces codeforces.com 문제 풀이 A번 문자열 전부 대문자 or 소문자로 변환 중복되지 않도록 새로운 문자열 만들기 MEOW와 일치하는지 확인 B번 대문자, 소문자를 나누어 갯수 세기 조건에 일치하는 만큼 더하기 남는 알파벳이 2개 이상이라면 k가 있는 만큼 더해주기 C번 보너스 카드일때 heapq에 삽입 (최대힙) 영웅카드일 경우에 heappop 후 점수 더하기 D번 문자열에 길이 - 1을 answer로 지정 문자열을 3개씩 골라서 팰린드롬이라면 answer -= 1 EFG 실패.. 결과 떡잎방법대 첫 출격
solved.ac Class 4레벨에 속한 문제이다. 문제 주소: https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 문제 해석 문제 풀이 먼저 주어진 입력을 잘 받도록 코드를 구현해야 한다. 임의의 두 점 사이의 거리 중 가장 긴 것을 구하기 위해서는 일반적으로 모든 노드를 dfs 탐색해야 한다. 하지만 이 경우 주어진 노드의 수가 10,000개 이므로 n^2의 시간복잡도에서 통과할 수 없다. 이러한 트리의 지름을 구하는 문제는 ..
solved.ac Class 4레벨에 속한 문제이다. 문제 주소: https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 문제 해석 확산과 공기청정기를 순서대로 작동하면 된다. 확산은 미세먼지가 존재하는 위치에 상하좌우로 5를 나눈 소수점을 제거한 값만큼 확산된다. 이때 확산할 공간이 없거나 확산 위치에 공기청정기가 존재한다면 확산할 수 없다. 확산이 되는 만큼 감소된다. (확산에서 미세먼지는 항상 보존된다.) 미세먼지의 양이 5미만이라면 확산되지 ..
solved.ac Class 4레벨에 속한 문제이다. 문제 주소: https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 문제 해석 문제 풀이 입력 범위가 1000 이기 때문에, lis 알고리즘이 아니라 2차원 dp를 사용해 가장 긴 증가하는 수열을 앞에서, 뒤집어서 두 번 구해주었다. 뒤집어서 구해준 값들을 다시 뒤집어 순서를 맞춰주고, 두 dp값들의 합이 최대가 되도록 하는 값 + 1이 답이 된다. 문제 코드 def solve(n, arr): # 앞에서 부터 가장 긴..
