열이의 개발블로그

https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 분석 각 집의 색은 이전, 이후의 집과 색이 달라야 한다. 집의 색이 정해진다면 비용을 누적하여 가장 작은 비용을 출력하면 된다. 기준이 없으므로 1번 집부터 색을 칠한다고 가정했을 때, 1번 집의 색이 빨강이라면 2번 집은 초록과 파랑 중 골라야하고 N번 집도 초록과 파랑 중 골라야 한다. 1149번: RGB거리 문제 위의 문제의 경우는 자기 자신의 바로 다음 ..

https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 문제 분석 팰린드롬(palindrome)이란? 팰린드롬[나무위키] 회문 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 회문(回文) 또는 팰린드롬(palindrome)은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열(sequence of characters) 등이다. 보통 낱말 사이에 있는 띄 ko.wikipedia.org 문제는 N개의 자연수 중 S번째 수부터 E번째까지의 수가 팰린드롬인지 ..

https://www.acmicpc.net/problem/1958 1958번: LCS 3 첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다. www.acmicpc.net 문제 분석 LCS란 최장 공통 부분수열이다. 만약 문자열이 두 개(예제 입력 1의 위 두 문자열)라고 가정하였을 때, 다이나믹 프로그래밍(DP)를 사용하여 쉽게 LCS를 계산할 수 있다. 위의 그림과 같이 두 문자열을 앞에 공백이 있는 이차원 리스트로 만든다. 그 후 이중 반복문을 돌면서 같은 문자열이 있는지 탐색한다. 1. 같은 문자를 만난 경우 이 때, 같은 문자를 만난다면 대각선 왼쪽 위에 있는 수에 1을..