https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 이 문제가 왜 DP를 이용하는지에 대한 이해를 도와주는 그림이다. start와 end가 같을 때, list[start+1, end-1]이 이미 팰린드롬이라면 list[start,end]가 팰린드롬인지 아닌지 바로 판별할 수 있기 때문이다. 1. 우선 dp 테이블을 하나 정의한다. ex) dp[i][j], i는 start를 의미하고 j는 end를 의미한다 2. 길이가 1짜리인 리스트 (= i와 j가 동일한) 는 모두 팰린드롬이다 3. 길..
https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 생각보다 까다로웠던 dp 문제이다. (사실 dp문제는 다 까다롭지만,,) dp[1], dp[2], dp[3]까지는 손쉽게 생각할 수 있다. dp[i]가 의미하는 바는 i번째 와인까지 마셨을 때 최대로 마실 수 있는 와인의 양이다. 1. 전전 와인 먹지 않고 전 와인과, 현재 와인 마시기 + 전전전 와인까지의 최댓값 2. 전 와인 먹지 않고 현재 와인 마시기 + 전전 와인까지의 최댓값 3. 전 와인까..
https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 알고리즘 수업에 나온 내용이 백준 문제에 있길래 풀어보았다. 우선 행과 열 값들을 저장해준다. 그런 다음 삼중 for문(O(n^3)) 을 이용해 값을 구해준다. 행렬곱셈의 순서는 다른 dp 문제들과 동일하다. 바텀 업으로 시작하여 값을 계산하고, 계산된 값을 저장한다. 그리고 그 계산된 값을 이용하여 답을 구하는 것이다. 행렬 곱셈순서를 구하기 위해서는 몇개를 곱할 것인지, 시작점은 ..
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 문제 설명 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하의 모든 부하들이 칭찬을 받는다. 모든 칭찬에는 칭찬의 정도를 의미하는 수치가 있는데, 이 수치 또한 부하들에게 똑같이 칭찬 받는..
