https://www.acmicpc.net/problem/2021 2021번: 최소 환승 경로 첫째 줄에 역의 개수 N(1≤N≤100,000), 노선의 개수 L(1≤L≤100,000)이 주어진다. 다음 L개의 줄에는 각 노선이 지나는 역이 순서대로 주어지며 각 줄의 마지막에는 -1이 주어진다. 마지막 줄에는 출발 www.acmicpc.net 디스코드방에서 추천받아서 풀어본 문제 일단 "최소" 라는 단어에서 다익스트라라는 감을 잡았다. 근데 같은 노선끼리는 이동거리를 0으로 해석해줄 수가 있어서, 사실상 같은 노선을 싹 뭉뚱그려서 하나의 무언가로 봐주는 과정이 필요하다 유니온 파인드 비슷한 느낌으로 노선 L개를 N+1번부터 각 노선당 한개의 노드를 할당해줬고, 각 역에서는 갈수있는 노선들을 이어줬다. 즉 ..

KMP P2 자력솔 헉!!!! https://www.acmicpc.net/problem/2401 2401번: 최대 문자열 붙여넣기 어떤 긴 문자열이 주어지고 여러 개의 짧은 문자열들이 주어질때 이때 짧은 문자열을 긴 문자열에 붙여 넣을때 가장 길게 붙여 넣는 경우를 찾아라. 단 이때 짧은 문자열들끼리는 교차 할 수 없 www.acmicpc.net 일단 처음 보고 한 생각은 KMP를 쓰더라도 브루트포싱은 힘들겠구나 였다. 문자열을 중복으로 넣을수 있다는 점에서 완탐을 하면 확실하게 시간초과임이 와닿을듯? 근데 이 문제는 긴 문자열 S에 어떤 짧은 문자열 s를 매칭 시킬 때, 매칭된 위치가 k라고 하면 S의 [0,k) 까지의 범위는 해당 문자열을 붙여넣던 말던 항상 값이 변하지 않는다. 앞서 문자열을 붙여넣..

실버골드 랜덤디펜스 BFS를 사용해서 풀어보았다. https://www.acmicpc.net/problem/12919 12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net 처음에는 S에서 시작해서 T로 문자열을 하나씩 붙여가면서 완탐을 돌릴 생각을 했는데, S.length() 가 1이고 T.length()가 50인경우에는 메모리초과가 발생하게 된다. 그래서 미리미리 불가능해보이는 경우의 수는 쳐낼생각을 해야 하는데, 생각을 정 반대로 바꿔서 T에서 시작해서 S로 문자열을 하나..

백랜디 도중에 만난 문제 세종정보올림피아드에서 비슷한 유형의 문제를 접했던 기억이 있어서 "케이크처럼" 쉽게 풀어보았다. https://www.acmicpc.net/problem/1374 1374번: 강의실 첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 www.acmicpc.net 강의 시작시간과 종료시간을 기준으로 탐색하면 10억번의 탐색을 필요로 하고, 시간초과를 받음이 매우 직관적으로 보인다 강의의 시작시간과 종료시간 사이에는 그 강의가 항상 있음이 보장 되기 때문에, 그 중간 시간에 대해서 탐색할 필요가 없다는게 시간 절약 방법의 핵..

백준랜덤디펜스 도중에 만난 문제 예전에도 지문을 한번 읽었던거같은데 바로 아이디어 떠올릴수있는거보면 실력이 늘긴 늘은거같아서 흐뭇하다 https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net lis임을 관찰해내기 어려워서 골드4라고 하는데, 개인적으로는 좀 빠르게 찾아낼 수 있었다. 처음에는 머지소트를 사용해서 교차횟수를 세는 문제인가? 라는 생각을 하고 시작했다. 근데 이 문제는 버블정렬처럼 인접한 두 원소를 swap 하는게 아니고, 저 멀리 떨어져있는 것들..

풀이법이 신기해서 가져와본 문제. https://www.acmicpc.net/problem/1052 1052번: 물병 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번 www.acmicpc.net 2의 제곱수 리터 만큼의 물이 들어있는 물병의 갯수가 K개 이하가 되도록 물병을 합쳐보는 문제. 처음에는 1리터짜리 물병 a개, 2리터짜리 물병 b개. 4리터짜리 물병 c개.... 이렇게 갯수별로 저장해보려고 했었는데 지나치게 뜬구름 잡는 내용인가 싶어서 태그를 까봤다. 태그에 "비트마스킹" 이 있는게 좀 결정적이었다고 생각한다. 위의 방법대로 갯수대로 저장을 하면, ..