mojo's Blog

문제 링크 => 11003번: 최솟값 찾기 (acmicpc.net) 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 우선순위 큐를 이용하는 문제이다. (덱을 활용해도 풀리는 문제) 앞과 뒷부분을 가르키도록 하는 변수 front, end를 선언하였다. 그리고 priority_queue pq 를 선언하여 첫번째에 배열값, 두번째에 인덱스값을 push하고 오름차순으로 정렬하도록 구현하였다. front ~ end 범위 내에 인덱스가 존재하는 경우 => 가장 작은 값이므로 출력한다. fr..

문제 링크 => 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..