Hello COCOBALL!

https://www.acmicpc.net/problem/15972 15972번: 물탱크 세로 길이가 N, 가로 길이가 M, 높이가 H인 물탱크가 있다. N, M, H는 모두 양의 정수이다. 은 세로 길이가 2, 가로 길이가 3, 높이가 5인 물탱크 모양을 보여준다. 에서 보듯이 물탱크 www.acmicpc.net SOLUTION 티어에 비해선 걱정했던거보다 쉬운 문제였다. 처음엔 입력을 처리하는 것도 골치아팠는데, vector를 쓰려다가 그냥 3차원 배열을 썼다. 배열 D에는 각 노드들의 상하좌우에 해당하는 위치에 구멍이 있는지 없는지가 저장되어 있다. 먼저 외부와 연결된 구멍이 1개 이상 있는 노드의 경우, 해당 노드의 수위는 구멍의 높이 중 최솟값으로 변경시켜준다. (외부와 연결되어 있기 때문에 항..

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/17371 17371번: 이사 $(\frac{2}{3}, \frac{1}{3})$으로 이사를 가면 가장 가까운 편의시설은 (0, 1)으로 거리는 $\frac{2\sqrt{2}}{3}$이고, 가장 먼 편의시설은 (-4, 1) 혹은 (4, -3)으로 거리는 둘 다 $\frac{10\sqrt{2}}{3}$이다. 두 거리의 www.acmicpc.net SOLUTION 처음에 티어랑 문제 보고 어려운 알고리즘 문제인 줄 알았다. 문제 풀이 방향 잡기가 어려웠는데, 그냥 주어진 편의시설 좌표들을 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/2304 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net SOLUTION 스택을 이용해 푼 문제다. 비가 올 때 물이 고이지 않게 오목한 부분이 없도록 만들기 위해서 왼쪽에서 오른쪽으로 가면서 한번, 오른쪽에서 왼쪽으로 가면서 한번 탐색을 해서 높이가 커지는 것들만 집어넣어 가면서 넓이를 계산했다. 두번의 탐색에서 높이가 가장 큰 것들의 높이는 같을것이고, x좌표가 같다면 1*높이, x좌표가 다르다면 가로*높이를 추가해줬다. 코드 #in..

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원짜리 동전들이 있..