기로에 서다

문제 www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 풀이 현재 보고있는 지시사항에서 각 각의 발의 위치 상태에 따라 이동하는 비용이 전부 다르므로 상태를 정의하여 dp를 사용하면 해결할 수 있습니다. 1. "dp[cmd_idx][left][right] : 현재 보고 있는 지시사항의 인덱스(cmd_idx)에서 왼발의 위치가 left, 오른발의 위치가 right일 때, 모든 지시 사항을 만족하는 데 사용되는 최소의 힘"이라고 ..

문제 www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 1. 연속된 세 집의 색깔을 결정하는게 아니라 연속된 두 집의 색을 결정해간다고 생각하면 다른 집들과 조건이 다른 첫 집의 색을 고정했을 때, 나머지 집의 가능한 색을 찾아 비용을 최소화하는 방법으로 생각할 수 있습니다. 2. "dp[cur][precolor] = 현재 cur번째 집의 색을 결정하고 있으며, 바로 전 집을 precolor로 칠했을 때 모든 집을 칠하는 최소..

문제 www.acmicpc.net/problem/20167 20167번: 꿈틀꿈틀 호석 애벌레 - 기능성 꿈틀꿈틀 호석 애벌레는 N 개의 먹이가 일렬로 나열된 나뭇가지를 오른쪽으로 기어가려고 한다. 시작하는 순간의 호석 애벌레가 0의 위치에 있고 i 번째 먹이는 오른쪽으로 i 초 기어가야 도달할 www.acmicpc.net www.acmicpc.net/problem/20181 20181번: 꿈틀꿈틀 호석 애벌레 - 효율성 꿈틀꿈틀 호석 애벌레는 N 개의 먹이가 일렬로 나열된 나뭇가지를 오른쪽으로 기어가려고 한다. 시작하는 순간의 호석 애벌레가 0의 위치에 있고 i 번째 먹이는 오른쪽으로 i 초 기어가야 도달할 www.acmicpc.net 20167 풀이 N의 상한이 20이기에 i번째 먹이를 먹었거나 안 ..

문제 www.acmicpc.net/problem/19576 19576번: 약수 가능 한 방법 중 하나로, a2를 12로, a3을 3으로 바꾸면 된다. www.acmicpc.net 문제 풀이 1. 약수관계를 생각해보면 1은 모든 수와 약수관계를 이루므로 와우매직을 사용하는 경우엔 1로 바꿔주면 된다. 2. 와우매직을 최소한으로 사용하기 위해선 기존의 수들이 최대한 많은 약수관계를 이뤄야하고, 이는 수들을 정렬했을 때 각 인덱스를 시작으로 해당 인덱스의 수와 다른 수들과의 약수관계를 이루는 길이를 구하고 그 중 최댓값을 n에서 빼주면 와우매직을 사용하는 최소횟수이다. 코드 #include using namespace std; int n, dp[5001]; vector a; int go(int cur) { i..