AquaplaneMode

문제 민오는 1번부터 N번까지 총 N개의 문제로 되어 있는 문제집을 풀려고 한다. 문제는 난이도 순서로 출제되어 있다. 즉 1번 문제가 가장 쉬운 문제이고 N번 문제가 가장 어려운 문제가 된다. 어떤 문제부터 풀까 고민하면서 문제를 훑어보던 민오는, 몇몇 문제들 사이에는 '먼저 푸는 것이 좋은 문제'가 있다는 것을 알게 되었다. 예를 들어 1번 문제를 풀고 나면 4번 문제가 쉽게 풀린다거나 하는 식이다. 민오는 다음의 세 가지 조건에 따라 문제를 풀 순서를 정하기로 하였다. N개의 문제는 모두 풀어야 한다. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다. 가능하면 쉬운 문제부터 풀어야 한다. 예를 들어서 네 개의 문제가 있다고 하자. 4번 ..

들어가기 앞서 이번 문제를 풀면서 Union-Find 알고리즘을 처음 익혔다. 다른 풀이를 보면 대부분 재귀함수로 푸는 경향이 있는데, 개인적으로 재귀함수를 굉장히 싫어하기 때문에 선호하는 방법으로 여러 번 풀었지만 전부 시간초과가 났다. 따라서 나의 알고리즘이 어떤 문제가 있었는지를 중심으로 본 문제를 정리하고자 한다. 문제 오늘은 신승원의 생일이다. 박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다. 공항에는 $G$개의 게이트가 있으며 각각은 1에서 $G$까지의 번호를 가지고 있다. 공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 $i$번째 비행기를 1번부터 $g_i$ (1 ≤ $g_i$ ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 ..

문제 피리 부는 사나이 성우는 오늘도 피리를 분다. 성우가 피리를 불 때면 영과일 회원들은 자기도 모르게 성우가 정해놓은 방향대로 움직이기 시작한다. 성우가 정해놓은 방향은 총 4가지로 U, D, L, R이고 각각 위, 아래, 왼쪽, 오른쪽으로 이동하게 한다. 이를 지켜보던 재훈이는 더 이상 움직이기 힘들어하는 영과일 회원들을 지키기 위해 특정 지점에 ‘SAFE ZONE’ 이라는 최첨단 방음 시설을 만들어 회원들이 성우의 피리 소리를 듣지 못하게 하려고 한다. 하지만 예산이 넉넉하지 않은 재훈이는 성우가 설정해 놓은 방향을 분석해서 최소 개수의 ‘SAFE ZONE’을 만들려 한다. 성우가 설정한 방향 지도가 주어졌을 때 재훈이를 도와서 영과일 회원들이 지도 어느 구역에 있더라도 성우가 피리를 불 때 ‘S..

문제 출처 : 2629번: 양팔저울 코드 참조 : https://source-sc.tistory.com/ 문제 풀이 해당 문제는 동적 계획법 (Dynamic Programming)으로 푸는 문제이다. 저울의 사용자는 추를 가지고 세 가지 작업 중 하나를 수행할 수 있다. 추를 왼쪽에 올린다. 추를 오른쪽에 올린다. 추를 올리지 않는다. 세 가지 작업을 모두 수행하는 DFS를 실행하여 문제를 해결한다. 코드 import sys input = sys.stdin.readline # 입력값 받기 num_pends = int(input()) # 추의 개수 (