알고리즘 문제풀이
-
[백준/BOJ] 2293번 동전 1 (C++)알고리즘 문제풀이/백준 2020. 12. 21. 19:58
www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net DP 유형의 문제입니다. 점화식을 도출해내기 위해서 동전의 종류가 1원, 2원, 5원이 있고 숫자 10을 만드는 경우의 수를 구한다고 했을 때 밑의 예시를 살펴보겠습니다. 1 2 3 4 5 6 7 8 9 10 1 1 1 1 1 1 1 1 1 1 1번부터 10번까지 dp 테이블을 만들고, 동전 1원으로 만들 수있는 경우를 살펴보면 전부 1개입니다. 그렇다면 다음으로 1원과 2원을 이용한 경우는 어떻게 되는지 살펴보..
-
[백준/BOJ] 18353번 병사 배치하기 (C++)알고리즘 문제풀이/백준 2020. 12. 21. 17:02
www.acmicpc.net/problem/18353 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net DP 유형의 문제로 LIS를 활용하는 문제입니다. 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 하므로, 이를 뒤집어 오름차순으로 변경하고 LIS의 최대값을 구해 전체 병사의 수에서 빼주면 되는 문제입니다. #include #include #include using namespace std; int dp[2001]; int main(void) { ios_base::sync_with_s..
-
[백준/BOJ] 11053번 가장 긴 증가하는 부분 수열 (C++)알고리즘 문제풀이/백준 2020. 12. 21. 16:59
www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net DP 유형의 문제로, LIS(Longest Increasing Subsequence)의 개념을 알게된 문제였습니다. #include #include #include using namespace std; int dp[1001]; int main(void) { ios_base::sync_with_stdio(false); cin.tie(0..
-
[백준/BOJ] 1912번 연속합 (C++)알고리즘 문제풀이/백준 2020. 12. 20. 13:41
www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net DP 유형의 문제입니다. n까지 연속되는 합을 더해가다가 0보다 작아졌을 때는 0으로 초기화 후 연속합을 구하는게 포인트입니다. 따라서 이를 점화식으로 나타내면 다음과 같습니다. dp[n] = max(0, dp[n - 1]) + v[n] 마지막으로 1~n까지 각 구간에서의 합 중 최대값을 출력하면 됩니다. #include #include #include using namespace std; int dp[100001]; i..
-
[백준/BOJ] 1149번 RGB거리 (C++)알고리즘 문제풀이/백준 2020. 12. 20. 12:46
www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net DP 유형의 문제입니다. 입력값의 각 열은 R, G, B 색깔, 행은 집의 수를 의미합니다. 문제의 조건은 결국 같은 색이 인접하면 안된다는 것을 의미합니다. 따라서 n번째 집의 색이 R, G, B 였을 때 n-1의 색이 다른 색이 되게끔, 최소값을 가지게끔 만들면 됩니다. 그런데 색깔에 따라 점화식을 만들어내야하므로, 2차원 dp배열을 이용하면 다음과 같은 점화식을 만들 수 있습니다. d..
-
[백준/BOJ] 14889번 스타트와 링크 (C++)알고리즘 문제풀이/백준 2020. 12. 19. 17:42
www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 삼성 역량 테스트 기출 문제 : DFS(조합) or 순열 next_permutation을 이용하여 팀을 나눠줍니다. (예를들어 0, 0, 1, 1 로 시작) 0은 start팀, 1은 link팀으로 나누어 각각의 합을 구하고 두 합의 차이의 최소값을 찾으면 간단히 해결할 수 있습니다. DFS를 이용하는 경우 조합을 구하여 true는 start팀, false는 link팀으로 나누어 동일하게 해결할 수 있습니다. #include #inc..
-
[백준/BOJ] 2579번 계단 오르기 (C++)알고리즘 문제풀이/백준 2020. 12. 19. 17:14
www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net DP 유형의 문제입니다. 마지막 계단을 오를 때 다음과 같이 두가지로 경우로 나눠서 생각합니다. 연속 O 도착 연속 X 도착 연속 O 도착인 경우, 그 전 계단을 오른 건 무조건 연속 X 입니다. 왜냐하면 연속이 되어버리면 3계단 연속이 되어버려 문제의 조건을 만족할 수 없게 됩니다. 그래서 연속 O 도착의 점화식은 다음과 같이 나타낼 수 있습니다. dp[n][1] = dp[i - 1][0] + v[i] 그러나 연속 X 도..
-
[백준/BOJ] 2133번 타일 채우기 (C++)알고리즘 문제풀이/백준 2020. 12. 19. 00:03
www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net DP 유형으로 이전에 풀었던 타일링 문제와 비슷한데, 살짝 어려워진 유형의 문제였습니다. 맨 오른쪽 끝에 하나를 놓는 경우 2*d[n - 1], 맨 오른쪽 끝에 두개를 놓는 경우 3*d[n - 2]로 다음과 같은 점화식을 도출해낼 수 있습니다. d[n] = 2*d[n - 1] + 3*d[n - 2] 그러나 주의할 점이 있는데 n = 4일 때 다음과 같이 새로운 모양이 생깁니다. 이러한 새로운 모양이 n이 4부터 짝수일 때마다 2개씩 생기는게, 이러한 경우를 고려하면 다음과 같은 점화식을 도출해낼 수 있습니다. d[n] =..