문제 풀이

[baekjoon 2294] 동전 2- DP(동적 프로그래밍) (C++)

www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 주어진 동전의 값을 이용해서 목표한 값을 동전 개수의 합으로 나타내는 경우 중 최소한의 동전 개수를 출력한다. 동전의 값보다 작은 숫자는 만들지 못한다. 동전의 값보다 큰 숫자는 크기가 n인 동전으로 구성할 수 있다. 그리고 그 이후에 크기가 n보다 큰 동전으로 그 숫자를 구성할 수 있다면 동전의 개수는 줄어든다. 즉, 5를 동전 1, 2, 5로 만들 수 있는 경우를 생각해보면 동..

[baekjoon 1149] RGB거리 (DP) (C++)

www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제는 빨강, 초록, 파랑으로 칠해져 있는 집 적혀있는 숫자의 합이 최소가 되도록 구하는 것이다. 규칙은 i번째 집은 i-1번째 또는 i+1번째 집과 같은 색으로 칠해져 있으면 안 된다. 즉, 만약 1번을 뽑았으면 다음 차례엔 1번을 뽑지 못한다는 것이다. 나는 3중 dp배열을 통해서 문제를 해결하려 했다. dp[i][n]에서 n은 각각 1번째, 2번째, 3번째 집을 의미하며 각각을 선택했..

[baekjoon 1806] 부분합 (투 포인터) (C++)

www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 시간제한이 0.5초로 매우 짧기 때문에, 부분합을 구하기 위해서 2중 for문을 돌면서 풀면 풀리겠지만 시간은 O(N^2)로 시간제한에 걸리게 된다. 따라서 이 문제는 O(N)의 시간 복잡도로 풀이가 가능한 두 포인터를 이용해야 한다. 두 포인터란 배열을 가리키는 포인터 인덱스 l, r (왼쪽, 오른쪽 맘대로)를 선언 후, 매번 조건과 비교하면서 왼쪽, 오른쪽 인덱스를 바꿔주며 배열을 탐색하는 것..

[baekjoon 1326] 폴짝폴짝 (BFS) (C++)

www.acmicpc.net/problem/1326 1326번: 폴짝폴짝 첫째 줄에 징검다리의 개수 N(1≤N≤10,000)이 주어지고, 이어서 각 징검다리에 쓰여 있는 N개의 정수가 주어진다. 그 다음 줄에는 N보다 작거나 같은 자연수 a, b가 주어지는 데, 이는 개구리가 a번 www.acmicpc.net 문제는 개구리가 징검다리를 뛰어다니는데, 그 징검다리에는 각각 숫자가 써져있고 개구리는 자신이 서있는 징검다리의 숫자의 배수만큼 점프할 수 있다. 즉, 10개의 징검다리에서 1 2 3 4 5 6 7 8 9 1 이 써져있고 2번에서 9번까지 가고 싶다면 처음 징검다리 2번의 경우 : 2가 써져있으므로 2의 배수인 4 6 8 10을 각각 한 번의 점프로 방문이 가능하다. 그 이후 10의 경우 : 1이 ..

[baekjoon 2447] 별 찍기 - 10 (재귀 호출) (C++)

www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 재귀를 이용해서 별 찍기 문제이다. 그림처럼 사이즈가 3일 때는 가운데만 뚫려있고, 나머지 case는 재귀적으로 주위에 이전 단계 도형이 그려지고 가운데가 뚫려있게끔 출력하면 된다. 사이즈가 27이면 주변이 위에 있는 사이즈 9의 도형이 둘러싼다. 처음엔 재귀를 이용하되, 함수 자체에서 cout을 하면 되겠다고 생각했지만, 개행을 해주면 재귀적으로 출력을 하기 힘들다고 판단했고, 2차..

[baekjoon 11729] 하노이의 탑 이동 순서 (재귀 호출) (C++)

www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 유명한 하노이의 탑 문제이다. 재귀를 하나하나 따라가며 이해해보려고 했는데 쉽지가 않았다. 재귀를 이용한 문제는 재귀의 모든 흐름을 파악하기보다는, 호출의 의미와 재귀 함수와 호출의 관계를 생각해야겠다. 하노이의 탑의 공식은 1. N-1개의 원판을 첫 번째 기둥에서 두 번째 기둥으로 옮기고 2. 마지막 하나 남은 원판을 첫 번째 기둥에서 세 번째 기둥으로 옮기고(출력) - 하나의 원판을 옮기는 경우..