mojo's Blog

문제 링크 => 1699번: 제곱수의 합 (acmicpc.net) 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 다이나믹 프로그래밍 문제이다. 자연수 N을 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구해야 하는 문제이다. 첫번째로 접근한 방법은 다음과 같다. d[1] = 1 / 1개 d[2] = d[1] + d[1] / 2개 d[3] = d[1] + d[1] + d[1] / 3개 d[4] = 4 / 1개 d[5] = d[4] + d[5-4] / 1 + 1 = 2..

문제 링크 => 2225번: 합분해 (acmicpc.net) 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 다이나믹 프로그래밍 문제이다. 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구해야 한다. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. => 이부분에서 dp 를 활용해야 한다는 것을 확인할 수 있다. 다음과 같은 시뮬레이션으로 dp를 유추해보도록 한다. n=20, k=1 인 경우 합이 20일 경우 => 20 / 1개 , dp[1][20] = 1 합이 19일 경우 => 19 / 1개 , dp[1][19] = 1 ... 합이 0일..

문제 링크 => 11440번: 피보나치 수의 제곱의 합 (acmicpc.net) 11440번: 피보나치 수의 제곱의 합 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 수학 + 분할 정복을 이용한 거듭제곱의 문제이다. 이문제는 2086번: 피보나치 수의 합 (acmicpc.net) 이걸 해결한다면 굉장히 쉬운 문제이다. 생각보다 이문제는 규칙성이 너무 쉽게 발견되서 금방 해결한 문제이기도 하다. 다음과 같이 규칙성을 찾아보도록 한다. (이때 Fibo(1)^2 = 1, Fibo(2)^2 = 1, Fibo(3)^2 = 4, Fibo(4)^2 = 9, Fibo(5)^2 = 25, Fibo(6)^2 = 64, Fibo(7)^..

문제 링크 => 2086번: 피보나치 수의 합 (acmicpc.net) 2086번: 피보나치 수의 합 첫째 줄에 a와 b(1≤a≤b≤9,000,000,000,000,000,000)이 주어진다. www.acmicpc.net 수학 + 분할 정복을 이용한 거듭제곱 문제이다. a, b값이 10^18 이라는 점을 고려했을때 logN 을 이용해야 한다는 것을 파악할 수 있다. 그래서 Fibo(n) 값을 어떻게 표현해야 효율적인지에 대해서 노가다를 좀 하더니 이러한 결과가 나왔다. Fibo(1) = 1 Fibo(2) = 1 Fibo(3) = 1^2 + 1^2 = 2 ( Fibo(1)^2 + Fibo(2)^2 ) Fibo(4) = 2^2 - 1^2 = 3 ( Fibo(3)^2 - Fibo(1)^2 ) Fibo(5) =..

문제 링크 => 16929번: Two Dots (acmicpc.net) 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 전형적인 DFS 문제이다. 점마다 DFS를 돌리면서 4번이상 이동함과 동시에 다시 재자리 점으로 돌아올 경우 Yes를 출력하도록 하면 된다. 이때 이동은 점의 색이 같아야 하며 인접하는 경우(좌우상하) 인 경우여야 한다. 그리고 방문처리의 초기화를 위해 별도의 init 함수를 생성하였다. 풀이 code #define _CRT_SECURE_NO_WARNINGS #include #incl..

문제 링크 => https://www.acmicpc.net/problem/13911 13911번: 집 구하기 첫줄에는 정점의 개수 V(3 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 300,000)가 주어진다. 그 다음 E줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u,v,w)가 순서대로 주어진다. 이는 u와 v(1 ≤ u,v ≤ V)사 www.acmicpc.net 다익스트라 문제이다. 이문제를 처음에 접근 했을때의 코드를 먼저 살펴보도록 한다. 시간 초과한 코드 #include #include #include #include using namespace std; using ll = long long; #define endl '\n' #define INF 200000001 vector ve..