어흥

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 1. 주의할 점 - DFS가 아닌 점화식을 통해 문제를 해결한다 2. 구현 - DP[][]를 통해 각 지점까지 거쳐간 숫자들의 합의 최대값을 저장한다 - 해당 지점에서 왼쪽 아래와 오른쪽 아래로 갔을 때 각 지점의 최대값을 갱신한다 - 가장 아랫변에 위치한 DP[][]값의 최대값을 반환한다 import java.util.*; import java.io.*; class Solution { static int dp[][]; pu..

문제 링크: https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 1. 주의할 점 - DP문제다. 백트레킹으로 접근할 생각하지 말자 - DP문제라는건 알았지만 점화식을 세우는게 쉽지 않다. 문제를 해결하고 다른사람들의 점화식을 확인해본 결과 나와 같은 점화식은 찾지못했다(내가 너무 어렵게 해결한것 같다). 2. 구현 - 우선 나는 0,1로 이루어진 비트라고 생각하고 접근했다(문제와 달리 행:2 , 열:N이라고 가정) - DP[숫자의 길이(=N)][마지막에서 2번째 번호][마지막 번호] 의 형태로 배열을 세웠다. ex)[N][0][0] : N의 길이면서 마지지막이 00으로 끝나는 수,..