문제 https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 문제풀이 n번 바퀴의 2번 index는 n+1번 바퀴의 6번 index와 인접하고 n번 바퀴의 6번 index는 n-1번 바퀴의 2번 index와 인접한다. 이 두 값을 먼저 update 한 후에, a번을 기준으로 왼쪽/오른쪽으로 2개의 for문을 통해 나머지 바퀴들을 탐색한다. a번과 바로 인접한 바퀴의 경우, a번과 반대 방향으로 돌아가야 하기 때문에 b에 -1을 곱해준 값을, 그 다..

문제 https://www.acmicpc.net/problem/13302 13302번: 리조트 수영이는 여름방학을 맞이하여 많은 놀이 시설이 있는 KOI 리조트에 놀러가려고 한다. 리조트의 하루 이용권의 가격은 만원이다. 하지만 리조트의 규모는 상상을 초월하여 모든 시설을 충분히 www.acmicpc.net 문제풀이 1일권, 3일권, 5일권과 그에 따른 쿠폰을 사용해서 리조트 이용을 위한 최소 비용을 구하는 dp 문제이다. bottom-up 방식으로 각각 날에 대해 dp 값을 갱신해주었다. dp[day][coupon]으로 2차원 dp 배열을 선언해서 이용권에 따라 쿠폰 값도 갱신해주었다. 1일권 구매 dp[i+1][j]=min(result+10000 , dp[i+1][j]) 3일권 구매 dp[i+k][j..

문제설명 https://www.acmicpc.net/problem/20923 20923번: 숫자 할리갈리 게임 첫째 줄에는 도도와 수연이가 가지는 카드의 개수 $N$($ 1 \leq N \leq 30\,000$)과 게임 진행 횟수 $M$($ 1 \leq M \leq 2\,500\,000$)이 주어진다. 둘째 줄부터 $N$개의 줄에는 띄어쓰기로 구분하여 도도와 수연 www.acmicpc.net 게임의 규칙은 흔히 알고 있는 할리갈리 게임의 규칙과 유사하다. 게임을 m번 반복했을 때 카드를 더 많이 가지고 있는 사람을 출력하는 문제 문제풀이 처음에는 도도와 수연이의 카드 덱과 그라운드 덱을 각각 2개씩 따로 만들어 풀었었는데, if 문의 조건도 복잡해지고 while문을 남발해서 시간초과가 났다 시간초과 문제..

문제 백준 17396 백도어 https://www.acmicpc.net/problem/17396 17396번: 백도어 첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000) 두 번째 줄에 각 분기점이 적의 시야에 보이는 www.acmicpc.net 문제풀이 백도어 하는데 걸리는 최단시간을 구하는 문제로 각각의 분기점으로 가는 시간이 가중치가 되는 다익스트라 문제 (n-1)번째 분기점은 값이 1이어도 갈 수 있는 분기점이기에 값이 0인 분기점과 동일 이를 제외한 분기점은 값이 1이라면 continue 해주기 개념정리 다익스트라는 최단경로 탐색 알고리즘으로 시작점으로부터 다른 모든 점까지의..