Hello COCOBALL!

https://www.acmicpc.net/problem/10251 10251번: 운전 면허 시험 만일 G 이하의 연료량으로 s에서 t까지 가는 것이 가능하다면 가능한 한 빨리 도착했을 때 걸리는 시간을, 불가능하다면 -1을 출력한다. www.acmicpc.net SOLUTION 4차원 dp 배열을 잡았는데 각각의 의미는 [grid에서의 x좌표][grid에서의 y좌표][현재 방향(0=왼쪽→오른쪽, 1=위→아래)][여기까지 오는데 방향이 바뀐 횟수] 다음과 같다. 각각의 행에서는, 예를들어 2번째 행에 있는 모든 node들은 2*2 = 4번 안에 접근이 가능하다. 손으로 그려보면 3행은 6번, 4행은 8번...임을 알 수 있고, 여기서 n행은 n*2회안에 접근이 가능하다는 것을 유추할 수 있다. (그래서 ..

https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net SOLUTION 점화식 : dp[i][j] += dp[i - 1][k]로 유도된다. 코드 #include using namespace std; int dp[1001][10]; int main() { int n; cin >> n; for (int i = 0; i

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net SOLUTION 점화식 0 -> arr[i][j] += arr[i - 1][j + 1] 1 ~ 8 -> arr[i][j] += arr[i - 1][j - 1] 9 -> arr[i][j] += arr[i - 1][j - 1] + arr[i - 1][j + 1] 코드 #include using namespace std; long long arr[101][10]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; c..

https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net SOLUTION 특정한 규칙을 찾아 점화식을 만들었고, 계산 중에 숫자가 터지지 않도록 (a+b) % M = ((a % M) + (b % M)) % M 다음과 같은 모듈러 연산의 특징을 이용하여 계산했다. 코드 #include using namespace std; long long arr[1000001]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); ar..

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net SOLUTION 전에 올린 동전 2 문제와 비슷한 방식으로 풀면 된다. 비슷하지만 약간 다른 문제라 살짝만 고치면 풀 수 있다. 동전 2 문제 풀이 코드 #include #include using namespace std; int price[1001]; int dp[1001]; int main() { int n; cin >> n; for (int i = 1; i > price[i]; dp[i] = -1;..

https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net SOLUTION 전에 올린 동전 2 문제와 비슷한 방식으로 풀면 된다. 동전 2 문제 풀이 코드 #include #include #include using namespace std; int dp[100001]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n..

https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net SOLUTION DP배열에 답을 구할건데, 최소값을 찾아야 하니까 우선 매우 큰 수로 초기화 한다. 초기의 배열 상태는 다음과 같다. Idx 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1원 INF INF INF INF INF INF INF INF INF INF INF INF INF INF INF INF 예제에서는 1,5,12원짜리 동전들이 있..