728x90 Baekjoon/[Code.plus] 알고리즘 기초 1／269 [BOJ/백준] 17404 RGB거리 2 ● [문제번호 17404] RGB거리 2 https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net ● 알아야 할 것 : 다이나믹 프로그래밍 ● 풀이 과정 : 1149 RGB거리 문제에서 1번 집과 N번 집의 색이 같지 않아야 한다는 조건이 추가되었다. ● 주의 할 것 : 1149 RGB거리 문제에서 좀 더 나아간 풀이일까 싶어서 고민했지만 구글링을 하니 조금 다르게 접근을 해야했다. 1149 RGB거리 에서 최소 비용을 구하.. 2021. 9. 9. [BOJ/백준] 2225 합분해 ● [문제번호 2225] 합분해 https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net ● 알아야 할 것 : 다이나믹 프로그래밍 ● 풀이 과정 : 알고리즘 기초 1/2 - 400 다이나믹 프로그래밍1 에 있던 문제이다. : 풀이를 떠올리다가 중복조합으로 풀면 되겠다고 생각했으나 계산과정을 어떻게 해야할지 의문이어서 구글링했다가 다른 방법으로 풀어야한다는 것을 알았다. : DP 풀이과정 (Bottom - Up) 1. 테이블 정의하기 → dp[k][n] : k개의 정수를 합하여 n을 만들수 있는 경우의 수 2. 점화식 찾기 → dp[K][N] = dp[K - 1][0] + dp[K.. 2021. 9. 9. [BOJ/백준] 1309 동물원 ● [문제번호 1309] 동물원 https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net ● 알아야 할 것 : 다이나믹 프로그래밍 ● 풀이 과정 : 알고리즘 기초1/2 - 401 다이나믹 프로그래밍1 (연습) 에 있던 문제이다. : 왼쪽, 오른쪽 자리에다가 추가로 사자를 배치 안하는 열을 고려하여 만들면 된다. : DP 풀이과정 (Bottom - Up) 1. 테이블 정의하기 → index까지 사자를 배치하는 총 경우의 수를 저장한다. // dp[index][0] : index자리에 사자 배치X // dp[index][1] : index자리에 사자 왼쪽 배치 // dp[index][2] .. 2021. 9. 9. [BOJ/백준] 2133 타일 채우기 ● [문제번호 2133] 타일 채우기 https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net ● 알아야 할 것 : 다이나믹 프로그래밍 ● 풀이 과정 : 여러 가지 경우의 수가 떠올라서 이렇게 하는게 맞나 싶어 구글링을 했더니 경우의 수를 많이 따지는 것이 맞았다. : DP 풀이과정 (Bottom - Up) 1. 테이블 정의하기 → dp[index] : index까지 타일로 채우는 경우의 수 2. 점화식 찾기 → 3X홀수 벽을 타일로 채울 수 없으므로 N이 홀수일 때는 0 출력 2일 때, 4일 때, 6일 때, 8일 때를 그려보면서 규칙을 찾아나간다. 풀이과정 참고.. 2021. 8. 5. 이전 1 2 3 4 ··· 18 다음 728x90
