2JINISHAPPY 2JINISHAPPY

https://www.acmicpc.net/problem/23030 23030번: 후다다닥을 이겨 츄르를 받자! 쿠기는 평소 지하철 최단 경로를 탐색하여 소요 시간을 알려주는 '후다다닥' 어플을 사용 중이다. 그러나 쿠기는 걸음이 너무 느려서 '후다다닥'이 알려주는 경로를 따라가면 항상 지하철이 떠 www.acmicpc.net 좌표가 아닌 지하철 (노선, 역)의 정보를 가진 다익스트라 문제 유형 실제 그래프에 더 가까우니까 사실 다익스트라의 취지(?)에 더 적합한 문제 유형 같당 노선의 역 개수를 입력받아 이차원 벡터를 만들어준 뒤 환승역이 있는 곳에는 이어지는 역에 대한 정보를 넣어주었다 역 사이의 거리는 일정하므로 역 번호의 차를 이용했고 다익스트라 풀이를 위해 해당 노선에 존재하는 환승역들에 대해 ..

https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 추천받아서 풀게된 무시무시한 플레 다익스트라 문제 일반 최단경로를 제외했을 때의 '거의 최단경로'를 구하는 문제다 그래서 음 prev를 구해서 체크해준 다음 다익스트라를 다시 돌리면 되지 않을까?생각했는데 접근 방법은 맞았다 위의 그림처럼 다익스트라를 수행하면서 prev를 저장하고(최단경로가 두 개 이상 존재할 수 있기 때문에 배열로 저장) 해당 경로를 삭제 or 접..

https://www.acmicpc.net/problem/22945 22945번: 팀 빌딩 능력치가 다 다른 개발자 $N$명이 팀 빌딩을 위해 한 줄로 서있다. 하나의 팀을 만들기 위해서는 개발자 2명이 반드시 모여야 한다. 개발자 A와 개발자 B가 팀을 만들 때 팀의 능력치는 아래와 같 www.acmicpc.net 오랜만에 푼 투포인터 문제 처음 문제를 봤을 때 에는 굉장히 어려워보였지만 코드로 옮기면서 생각보다 짧은 코드가 나왔다 팀 능력치를 구하는 부분에서 min(개발자 A의 능력치, 개발자 B의 능력치)를 구하게 되는데 구간이 줄어드는 로직에서는 (A와 B 사이의 개발자 수)는 무조건 줄게 되므로 left, right 포인터를 옮길 때 팀 능력치를 최대로 할 수 있도록 포인터를 이동시켜주어야 한다..

https://www.acmicpc.net/problem/22955 22955번: 고양이 도도의 탈출기 첫째 줄에 방의 높이 $N$ ($ 2 \leq N \leq 1\,000$)과 방의 너비 $M$ ($ 2 \leq M \leq 1\,000$)이 주어진다. 둘째 줄부터 $N$개의 줄에 공간의 상태가 주어진다. 공간의 상태는 $C$, $D$, $E$, $F$, $L$, $X$로 이루 www.acmicpc.net 재밌는(화나는) 다익스트라 문제 ~~ ㅎㅎ 이 문제에서 WA 많이 받았지만 깨달은게 있어서 도움이 많이 됐따 priority queue를 정의할 때 comparator(operator)의 정의가 잘못되었었다 ..ㅠ min heap으로 생성해야 하는데 max heap으로 생성되어서 WA를 받았었고 ...

https://www.acmicpc.net/problem/22939 22939번: 쿠키크루 밀가루반죽으로 잘 구워진 킴쿠키는 광활하고 평평한 들판 위에 세워진 쿠키나라의 시민이다. 킴쿠키는 케이크나라의 침략으로 어려워진 쿠키나라를 지키기 위해 할 수 있는 일이 없을까 늘 고 www.acmicpc.net 단어가 안 읽혀서 재밌는 문ㄴ제 ㅎㅎ 최단거리하면 자동으로 BFS와 연관짓게 되는데, 그러한 부분을 역으로 주의해야 한다 이 문제에서는 장애물도 없고, 이동하는 데에 아무런 제약이 없기 때문에 거리를 단순히 맨해튼 거리로 구해주면 시간복잡도가 O(1)로 간단하다 따라서 모든 지원분야에 대해, 모든 정점 방문 가능 순서에 대해 전부 구해주면 되기 때문에 브루트 포스 ~~ import sys from iter..

https://www.acmicpc.net/problem/22953 22953번: 도도의 음식 준비 첫째 줄에 요리사의 수 $N$ ($1 \le N \le 10$), 만들어야 할 음식의 개수 $K$ ($1 \le K \le 1\,000\,000$), 격려해줄 수 있는 횟수 $C$ ($0 \le C \le 5$)가 주어진다. 둘째 줄에 길이가 $N$인 정수 수열 $A$가 주어 www.acmicpc.net 입국심사에서 백트래킹을 이용한 조합을 추가한 문제 ❗ 격려의 최대 회수가 5이기 때문에 격려해줄 수 있는 모든 경우를 시뮬레이션 한 뒤 이진탐색으로 값을 구해주면 된당 import sys input=sys.stdin.readline n,k,c=map(int,input().split()) a=list(map..

https://www.acmicpc.net/problem/3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 오랜만에 다시 푼 이진탐색 문제 입국심사 loop invariant에 대해 알고난 뒤에는 탐색 범위 설정에 유의하고 나니 설계도 더 명확하게 되고 잘 풀리는 느낌이다 대부분의 이진탐색에서 공통적으로 적용되는 조건인 left < right를 제외하면, 이 문제에서는 left일 때에는 모든 사람이 통과하는 것이 불가능하고 right일 때 에는 모든 사람이 통과하는 것이 가능해야 한다. ..

https://www.acmicpc.net/problem/21941 21941번: 문자열 제거 지우고 싶은 문자열 $S$와 지울 수 있는 문자열 $A_{1}$, $A_{2}$, ..., $A_{M}$이 주어진다. 문자열 $A_{i}$들은 각자 $X_{i}$라는 점수를 가진다. 이 때, 문자열 $S$를 삭제 연산을 이용하여 모두 제거하려 www.acmicpc.net 아주 고생고생고생한 DP문제 첫 번째 접근: 원래 문자열에서 해당하는 문자열을 삭제하고 중간 문자열들에 대한 최대 점수를 DP로 저장하는 방식(🔥시간초과🔥) import sys sys.setrecursionlimit(10**6) input=sys.stdin.readline def func(origin): global d,cache if len(..