https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net DP문제이다. 여느 DP문제가 그렇듯, 탑다운이 아니라 바텀업으로 풀어야한다. 이 문제의 점화식은 아래 3가지 조건을 만족해야한다. 점화식을 f(x)라 하자. 1. f(x) = f(x-1) + 1 --> 1을 더해서 만드는 경우 2. if x % 3 == 0, f(x) = f(x/3) + 1 --> x가 3으로 나눠질 때 3. if x % 2 == 0, f(x) = f(x/2) + 1 --> x가 2로 나눠질 때 ※ 여기서 더하기 1은 경우의 수가 하나 증가함을 의미한다!! 예를 들어 설명해보자면, 우..
https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 알고리즘 수업에 나온 내용이 백준 문제에 있길래 풀어보았다. 우선 행과 열 값들을 저장해준다. 그런 다음 삼중 for문(O(n^3)) 을 이용해 값을 구해준다. 행렬곱셈의 순서는 다른 dp 문제들과 동일하다. 바텀 업으로 시작하여 값을 계산하고, 계산된 값을 저장한다. 그리고 그 계산된 값을 이용하여 답을 구하는 것이다. 행렬 곱셈순서를 구하기 위해서는 몇개를 곱할 것인지, 시작점은 ..
https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 동전1과 유사한 DP문제이다. DP는 점화식을 세우는 것이 중요한데, 이 점화식을 찾기 위해 문제의 예제를 이용해보자. i원을 만들기 위해서 필요한 동전의 수를 dp배열에 저장할 것이다. 0원을 만들기 위해서는 동전 0개가 필요하다 -> dp[0]=0; 1원을 만들기 위해서는 1원짜리 동전 1개가 필요하다 -> dp[1]=1; 2원을 만들기 위해서는 2원짜리 동전 2..
https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 오랜만에 푼 DP(다이나믹 프로그래밍)문제다. 우선 삼각형을 입력 받아준다. 입력값들의 길이가 1,2,3,... 순으로 증가하므로 2차원 벡터를 이용해 입력 받았다. 그런 다음, 초기값을 설정해주는 것이 중요한데 dp[1][0]은 삼각형의 맨 첫번째 값(=꼭대기 값)이고 dp[1][1]은 원래 존재하지 않는 값이지만 점화식을 생성 및 이용하기 위해 0으로 설정해주었다. 초기값(삼각형 1층)에 대한 설정이 끝났으므로, 그 아래 줄인 삼각형 2층부터 점화식을 이용해 최대값..
https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 우선 이 문제는 RGB거리1의 확장판이다. 직전에 고른 색만 고를 수 없는 것이 아니라, 1번째 집과 N번째 집의 색도 달라야 하므로 원형문제라고 볼 수 있다! 우선, RGB색으로 칠하는 비용을 2차원 배열에 모조리 저장한다. for문을 3번 돌려서 1번 집이 R, G, B 색을 차례로 하나씩 선택하는 경우의 최솟값을 계산한다. 1번 집이 만약 Red를 골랐다면, ..
https://www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 문제분석 분류 DP, 그래프, 트리, bfs-dfs, 트리에서의 DP 문제 설명 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하의 모든 부하들이 칭찬을 받는다. 모든 칭찬에는 칭찬의 정도를 의미하는 수치가 있는데, 이 수치 또한 부하들에게 똑같이 칭찬 받는..
