Doby's Lab

https://www.acmicpc.net/problem/26125 26125번: 두 도로 첫 번째 줄에 교차로의 수 $N$, 기존 도로의 수 $M$, 집의 교차로 번호 $S$, 회사의 교차로 번호 $T$가 공백으로 구분되어 주어진다. ($2\leq N\leq 300$; $0\leq M\leq 3\ 000$; $1\leq S,T\leq N$; $S\neq T$) 이후 $M$개 www.acmicpc.net Level: Gold III Solved By: Floyd Warshall 각 쿼리마다 다익스트라를 쓰기에는 총 시간 복잡도는 O(Q * ElogV)로 시간 초과를 받게 됩니다. 그래서 오프라인 쿼리 같은 방법이 있을까 했지만, 떠오르지 않았습니다. 여기서 문제점은 '최단 경로들을 가지고 있는 배열이나 ..

https://www.acmicpc.net/problem/26124 26124번: 조명 배치 $(1,1)$, $(1,3)$, $(4,5)$ 위치에 각각 밝기 $3$, $5$, $3$의 조명을 설치하면 설계도와 동일한 미로를 만들 수 있다. www.acmicpc.net Level: Gold V Solved By: BFS, Implementation 구현이 꽤 어려운 문제였습니다. 아이디어는 꽤 직관적입니다. BFS를 통해 현재 좌표값에서 조명을 켤 수 있는가, 없는가를 알아냅니다. 켤 수 있다면, check 2차원 배열을 통해 조명으로 비춘 지역들을 check 해주었습니다. 그리고, 켤 수 없는 경우에는 이미 BFS를 진행하는 동안 좌표값들을 여러 개 방문 체크를 했었는데 어떻게 해야 할지 고민했습니다. ..

https://www.acmicpc.net/problem/26123 26123번: 외계 침략자 윤이 외계인 윤이는 지구를 정복하고자 세계의 중심 도시인 울산을 침략했다. 울산에는 $N$개의 빌딩이 일렬로 늘어서 있고, 왼쪽에서 $i$번째 건물의 높이는 $h_i$이다. 윤이는 울산을 파괴하기 위해 www.acmicpc.net Level: Silver IV Solved By: Priority Queue, Prefix Sum h값들을 받으면서 MaxHeap(Priority Queue)에 넣어줬습니다. 이유는 레이저를 쏘며 높이를 깎아가는 데에 있어 h-1이 다음 레이저를 쏠 때 높이이기 때문에 높이를 깎는 과정에서도 다음 높이(다음 최댓값)를 알기 위해 우선순위 큐를 사용했습니다. 즉, 우선순위 큐는 현재 깎..

https://www.acmicpc.net/problem/26122 26122번: 가장 긴 막대 자석 막대 자석 문자열은 문자 N과 S로만 구성되면서 다음과 같은 조건을 만족하는 문자열이다: 막대 자석 문자열에 등장하는 N의 개수와 S의 개수는 동일하며, 문자열의 앞쪽 절반을 구성하는 문자는 www.acmicpc.net Level: Silver V Solved By: Stack, Implementation 확실히 다른 분들의 풀이를 보니 더 깔끔한 풀이들이 존재합니다. 스택을 사용할 필요도 없었던 거죠. 급한 마음을 다루는 연습이 필요하다고 생각합니다. 풀이는 이렇습니다. 문자열을 for문을 통해 탐색하면서 해당 문자에 대한 스택에 1을 담아줍니다. 그리고, 진행을 하면서 앞 전 문자와 다르다면 스택의 ..

https://www.acmicpc.net/problem/6185 6185번: Clear And Present Danger There are 3 islands and the treasure map requires Farmer John to visit a sequence of 4 islands in order: island 1, island 2, island 1 again, and finally island 3. The danger ratings of the paths are given: the paths (1, 2); (2, 3); (3, 1) and the reverse p www.acmicpc.net Level: Gold V Solved By: Floyd Warshall 특정 sequence를 지나쳐..

https://www.acmicpc.net/problem/17134 17134번: 르모앙의 추측 첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100,000)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 홀수이고, 5 < N ≤ 1,000,000을 만족한다. www.acmicpc.net Level: Platinum I Solved By: FFT FFT 관련 문제 중 을 활용한 문제입니다. (https://draw-code-boy.tistory.com/459) Golf Bot 문제의 아이디어와 비슷하기 때문에 이에 관해서는 링크를 참고하시기 바랍니다. 케이스마다 소수를 구하기에는 번거롭기 때문에 N의 최대 범위인 1,000,000까지는 소수를 모두 구해놓습니다. 그리고, 세미 ..

https://www.acmicpc.net/problem/1417 1417번: 국회의원 선거 첫째 줄에 후보의 수 N이 주어진다. 둘째 줄부터 차례대로 기호 1번을 찍으려고 하는 사람의 수, 기호 2번을 찍으려고 하는 수, 이렇게 총 N개의 줄에 걸쳐 입력이 들어온다. N은 50보다 작거나 같 www.acmicpc.net Level: Silver V Solved By: Priority Queue, Greedy 아마 우선순위 큐라는 키워드가 없었다면 문제를 푸는데 어려움을 겪었을 것 같습니다. 1번의 value를 따로 받고 최댓값 우선순위 큐를 선언하여 나머지 value들을 넣어줍니다. 그러면 최댓값을 순서로 우선순위 큐에 담겨 있습니다. 1번의 value와 우선순위 큐의 top과 비교를 하며 크거나 같다..

https://www.acmicpc.net/problem/1057 1057번: 토너먼트 김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 www.acmicpc.net Level: Silver III Solved By: Recursive Call 이번 문제에는 함정이 숨어있었습니다. 답이 -1이 나오는 경우는 없습니다. 둘은 만나기 전까지 계속 이기기 때문에 어디선가 떨어질 이유가 없습니다. 그리고, 이 문제는 단순한 재귀로 풀 수 있을 거 같았습니다. a, b를 각각 2로 나누고 반올림하면 a, b각각 다음 번호가 주어집니다. 둘의 번호가 같아질 때 둘은 붙었다는 뜻..