어흥

문제 링크: https://www.acmicpc.net/problem/9207 9207번: 페그 솔리테어 문제 페그 솔리테어는 구멍이 뚫려있는 이차원 게임판에서 하는 게임이다. 각 구멍에는 핀을 하나 꽂을 수 있다. 핀은 수평, 수직 방향으로 인접한 핀을 뛰어넘어서 그 핀의 다음 칸으로 이동하는 것만 허용된다. 인접한 핀의 다음 칸은 비어있어야 하고 그 인접한 핀은 제거된다. 현재 게임판에 꽂혀있는 핀의 상태가 주어진다. 이때, 핀을 적절히 움직여서 게임판에 남아있는 핀의 개수를 최소로 하려고 한다. 또, 그렇게 남기기 위해 필요한 최소 이동횟수를 구하는 프 www.acmicpc.net 1. 주의할 점 - 백트레킹을 통해서 구현한다(핀의 최대 개수: 8) - 맵을 바꾼 후, 다시 돌아왔을 때 맵을 복구하..

문제 링크: https://www.acmicpc.net/problem/1477 1477번: 휴게소 세우기 첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. N은 100보다 작거나 같으며, M도 100보다 작거나 같다. L은 100보다 크거나 같고, 1000보다 작거나 같다. 모든 휴게소의 위치는 중복되지 않으며, N+M은 L보다 작다. 둘째 줄에, 휴게소의 위치가 공백을 사이에 두고 주어진다. www.acmicpc.net 1. 주의할 점 - 시작지점과 끝지점(고속도로의 길이)도 포함해야한다. - 이분탐색으로 해결한다. 2. 구현 - 첫 번째 구현방법: 구간과 구간사이의 길이를 구해서 우선순위큐에 적재한다. 우선순위큐의 Top에 있는 원소를 뽑아서 반..

문제 링크: https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 1. 주의할 점 - DP문제다. 백트레킹으로 접근할 생각하지 말자 - DP문제라는건 알았지만 점화식을 세우는게 쉽지 않다. 문제를 해결하고 다른사람들의 점화식을 확인해본 결과 나와 같은 점화식은 찾지못했다(내가 너무 어렵게 해결한것 같다). 2. 구현 - 우선 나는 0,1로 이루어진 비트라고 생각하고 접근했다(문제와 달리 행:2 , 열:N이라고 가정) - DP[숫자의 길이(=N)][마지막에서 2번째 번호][마지막 번호] 의 형태로 배열을 세웠다. ex)[N][0][0] : N의 길이면서 마지지막이 00으로 끝나는 수,..

문제 링크: https://www.acmicpc.net/problem/13459 13459번: 구슬 탈출 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다. 입력되는 모든 보드 www.acmicpc.net 1. 주의할 점 - 최대 10번만 기울일 수 있다. 10번 이전에 구멍을 도착한다면 더 이상 확인할 필요가 없다. - ..

문제 링크: https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대이다. (0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10) 입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않는다. 드래곤 커브는 서로 겹칠 수 있다. 방향은 0, 1, 2, www.acmicpc.net 1. 주의할 점 - 회전행렬을 진행하지만 Y값이 위로 가면 -1, 아래로 가면 +1이 되므로 기존의 회전행렬과 다르다...

문제 링크: https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 출발 도시의 번호가 주어지고 그 다음에는 도착 도시의 번호, 그리고 마지막에는 이 도로를 지나는데 걸리는 시간이 주어진다. 도로를 지나가는 시간은 10,000보다 작거나 같은 자연수이다. 그리고 m+3째 줄에는 지도를 그리는 사람들이 www.acmicpc.net 1. 주의할 점 - 위상정렬 혹은 다익스트라로 풀 수있는 문제지만 나는 다익스트라로 해결했다. - 우선, 다익스트라를 지금까지..

문제 링크: https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 가수의 수가 나오고, 그 뒤로는 그 가수들의 순서가 나온다. N은 1이상 1,000이하의 정수이고, M은 1이상 100이하의 정수이다. www.acmicpc.net 1. 주의할 점 - N과 M을 입력받은 다음, 각 보조PD가 정한 그룹수(Val), 그룹 순서가 차례대로 주어진다. 하지만 Val에 대한 어떠한 정보도 주어져 있지 않다. Val이 1인 경우 이후에 그룹이 1개만 나와서 순서에 의미..

문제 링크: https://www.acmicpc.net/problem/6118 6118번: 숨바꼭질 문제 재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재서기는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2 > target; tmp.idx = start; tmp.val = 1; v[target].push_back(tmp); tmp.idx = target; v[start].push_back(tmp); } for (int i = 1; i dist[cidx]+nv) { dist[next] = dist[cidx] + nv; tmp.idx = next; tmp.val = cv + nv; pq.push(tmp); } } } int maxi = dist[2], idx = ..