DP

1. 문제 설명링크 : https://www.acmicpc.net/problem/11492. 풀이 과정문제 해결의 흐름  우선, 문제 설명을 읽고 나서 DP 문제일 거 같다는 느낌이 강하게 들었습니다. 동적계획법, DP(Dynamic Programming)이란?중복되는 계산 결과를 저장하여 복잡한 문제를 더 작은 하위 문제들로 나누어 해결하는 기법입니다.이 기법은 다음 2가지 특징을 가진 문제에서 주로 사용됩니다!최적 부분 구조 : 문제를 작은 부분 문제들로 나누어 부분 문제들의 최적해를 구하여 최종적으로 전체 문제의 최적해를 구할 수 있는 구조 중복 부분 문제 : 동일한 부분 문제가 여러 번 반복되어 나타나는 구조 이 문제를 DP로 접근해야하는 이유는 이웃한 집의 색깔은 서로 달라야하는 조건 하에 모든..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 설명 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 풀이 과정 나의 풀이 ① 처음 이 문제..

https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 문제 설명 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다. 풀이 과정 나의 풀..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 문제 설명 풀이 과정 나의 풀이 ① 이 문제에서 직관적으로 파악한 것은 '위에서 아래로 순차적으로 진행되는 과정 속에서 최대인 경우를 찾는 것이니깐... DP문제인가...?'였다. ② DP문제인듯한 느낌을 받은 상태에서 예제문제의 과정을 직접 수행해보며 확인해보았다. 위에서 아래로 내려오며 빨간 O표 부분은 과정 속에서 최선의 방법이고, 빨간 X표 부분은 과정 속에서 버려지는 부분이다. ③ 아이디어 열기 (1) 입력값 처음 입력되는 값인 5값은 5줄의 삼각형 크기의 숫..