Dynamic Programming 썸네일형 리스트형 [백준 16639] 괄호 추가하기 3 (Java) 문제 링크 : www.acmicpc.net/problem/16639 16639번: 괄호 추가하기 3 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net 풀이 dfs로 완탐하는 방식으로 시도하다가 경우가 너무 많아서 자력으로 풀지 못했다. 다른 분의 블로그를 참고하여 해결할 수 있었다. DP 방식을 통해 풀이가 가능했는데, 2차원 배열을 생성하고 i번 째부터 j번 째 숫자들을 포함한 연산 결과들의 최솟값, 최댓값을 구했다. 최종적으로 최댓값을 구하는 것이지만, 연산 숫자가 음수 * 음수 인 경우 최댓값의 후보가 될 수 있기 때문.. [백준 11057] 오르막 수 (Java) https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다. www.acmicpc.net 접근 방법 전형적인 DP문제라고 하는데 역시나 아직 많이 부족함을 느낀다. 2차원배열을 사용한다. dp[N][0~9]로 수의 길이가 N번일 때, 마지막 자리수가 0 ~ 9 경우의 개수를 각각 담는다. 우선 dp[1][0~9]는 모두 1로 따로 설정을 해둔다.. 이전 1 다음
