복습노트 복습노트

문제 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 상근이와 창영이가 주어진 n개의 돌을 서로 번갈아 돌아가면 1개 또는 3개의 돌을 가져올 수 있는데 마지막으로 돌을 가져가는 사람이 이기는 게임입니다. 여기서 돌의 갯수 n이 주어졌을 때 이기는 사람을 구하는 문제입니다. 선공은 항상 상근이가 합니다. dp로 접근하였습니다. dp[x] : 돌이 x개 있는 게임판에서 선공이 이긴다면 true, 아니라면 false를 저장합니다. 초기 조건은 dp[1] = true, dp[2] = false, dp[3] = true로 잡아줍니다. dp[x-1]이 false이거나 dp[x-3]이 false이면 dp[x]는 true이고, 아니라면 dp[..

문제 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net n개의 도시들이 주어지고 도시와 도시간의 이동비용을 알려주고 임의의 시작점에서 모든 도시들을 순회하는데 최소의 금액으로 순회하는 비용을 출력하는 문제입니다. 도시와 도시간의 이동은 쌍방향이고 1번도시에서 2번도시로 갈때의 비용과 2번도시에서 1번도시로 갈때의 비용은 서로 다릅니다. 또한 한번 방문한 도시는 다시 방문할 수 없고 마지막으로 방문했던 도시는 맨 처음 도시로 돌아와야 합니다. 먼저 n의 범위가 최대 16으로 ..

문제 5934번: Visiting Cows After many weeks of hard work, Bessie is finally getting a vacation! Being the most social cow in the herd, she wishes to visit her N (1 HTML 삽입 미리보기할 수 없는 소스 main 함수에서 dfs(1, 0)이 실행된 상태 입니다. 첫번쨰 인자로는 현재 방문한 노드 번호가 들어가고 두번째 인자로는 현재 선택된 노드의 부모 노드가 들어갑니다. 따라서 지금 1번 노드 부터 살펴보는 것입니다. 2번째 줄을 보면 dp[x][1] = 1로 초기화 해줍니다. 왜냐하면 [1]은 자기 자신을 무조건 방문하기 때문입니다. 6번째 줄을 보면 dp[x][0] += max(..

문제 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 최상단 루트 노드가 주어지고 트리의 연결 정보가 주어졌을 때 노드의 번호를 입력하면 입력된 노드 번호를 포함한 subtree의 갯수를 출력하는 문제입니다. 예를 들어 루트 노드가 5이고 입력된 노드가 5, 4, 8 이라면 답은 각각 9, 4, 1 이 됩니다. 먼저 트리의 정보를 백터의 인접리스트 형태로 저장해줍니다. HTML 삽입 미리보기할 수 없는 소스 이제 각 노드마다 subtree의 갯수 정..

문제 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 수열이 주어지면 증가하는 부분수열중 길이가 가장 긴 길이를 구하는 문제입니다. 예를들어 {10, 20, 10, 30, 20, 50} 에서 가장 길이가 긴 수열은 {10, 20, 10, 30, 20, 50} 으로 총 길이가 4입니다. 수열 {10, 20, 10, 30, 20, 50} 에서 case를 나누어서 생각해보겠습니다. 1) 먼저 가장 첫번째 수열만 보면 그냥 그대로 '10' ..

문제 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 집에 빨간색이나 초록, 파란색으로 칠할 수 있는데 서로 붙어 있는 집은 같은 색을 칠하면 안됩니다. 먼저 각각 집에 대해서 가격을 저장해야 합니다. 1 = 빨간, 2 = 초록, 3 = 파랑 price[n][1] = n번째 집을 빨간으로 칠하는데 드는 비용입니다. HTML 삽입 미리보기할 수 없는 소스 이제 점화식을 세우겠습니다. 우리는 총 3가지의 경우의 수를 세울 수 있습니다. 처음에 집의 색을 선택하는 경우가 3가지 이기 때문입니다..

문제 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 계단을 1계단이나 2계단 오를 수 있는데 최종적으로 n번째 계단에 도달했을 때 획득 할 수 있는 최대점수를 구하는 문제 입니다. 연속적으로 3계단을 밟는건 불가능합니다. 여기서 상태(status)를 표현하는 방법으로 2차원 배열을 사용하였습니다. 현재 밟고 있는 계단이 이전에 1계단을 밟고 왔는지, 2계단을 밟고 왔는지 표현해 주어야합니다. 예를 들어 dp[n][k] 라는 의미는 현재 n번째 계단에 있는데 k계단을 밟고 왔다는 의미입니다. 여기서 점화식을 세워주면 dp..

문제 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net n이 주어지면 n을 3으로 나누거나 2로 나누거나 1을 빼든가 해서 1로 되게하는 연산의 합이 최소를 구하는 것입니다. 1 ≤ n ≤ 1000000 예를 들어 n이 10이면 (10 -> 9 -> 3 -> 1) 총 3번의 연산이 최소가 됩니다. bottom-up 방식으로 dp를 이용해 해결하였습니다. 1) n이 2로 나누어떨어지면 dp[n] = dp[n-1]과 dp[n/2] 중에서 작은 값에다가 1을 더해줍니다. 2) n이 3으로 나누어 떨어지면 dp[n] = dp[n-1]과 dp[n/3] 중에서 작은 값에다가 1을 더해줍니다. 3) n이 2와 3 모두 나누어 떨어지면 d..