DP

문제 링크 : https://www.acmicpc.net/problem/1042210422번: 괄호‘(‘, ‘)’ 문자로만 이루어진 문자열을 괄호 문자열이라 한다. 올바른 괄호 문자열이란 다음과 같이 정의된다. ()는 올바른 괄호 문자열이다. S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호 문자열이다. S와 T가 올바른 괄호 문자열이라면, 두 문자열을 이어 붙인 ST도 올바른 괄호 문자열이다. (()())()은 올바른 괄호 문자열이지만 (()은 올바른 괄호 문자열이 아니다. 괄호 문자열이 주어졌을 때 올바른 괄호 문자열인지 확인하는 방법은 여러 www.acmicpc.net문제 설명괄호 문자열의 길이가 주어졌을 때, 올바른 괄호 문자열의 개수를 구하는 문제이다.출력에서 10억+7로 나눈 나머지를 출력..

문제 링크 : https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 문제 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 www.acmicpc.net 문제 요약 여러 파일들이 주어졌을 때 파일들을 두 개씩 합쳐서 여러 장들이 연속이 되도록 파일을 합쳐나가 최종적으로..

문제 링크 : https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집도 이웃이다. 각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠하는 비용의 최솟값을 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 다이내믹 프로그래밍 문제입니다! RGB거리에 사는 사람들은 빨강, 초록, 파랑 3가지 색 중 하나로 집을 칠해야하는데, 인접한 집의 색이 같으면 안된다. 따라서 i번째 집의..

문제 링크 : https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 풀이 다이내믹 프로그래밍 문제입니다! 2X1 칸에 사자를 배치하는 경우는 왼쪽 사자 오른쪽 사자 사자 없음 세 가지이며, 사자들은 가로,세로에 붙어있을 수 없다. 각각의 경우를 0,1,2로 표현했을 경우 d[i][j] = i칸에 j상태의 사자가 있을 경우 사자 배치의 경우의 수 라고 표현 가능하며 각각 d[i][0] = d[i-1][1] + d[i-1][2] d[i][1] = d[i-1][0] + d[i-1][2] d[i][2] = d[i-1][0] + d[i-1][1] + d[i-1][2] 이다. 따라서 정답은 d..