코딩공작소

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 어렵지 않은 DP. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include #include #include using namespace std; int solution(vector triangle) { int answer = 0; vector DP = triangle; int h = triangle.size(); for(int i=1;i

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지 www.acmicpc.net 처음에는 dfs로 풀었었다... 하지만 맵의 크기가 500X500.. 상하좌우.. 즉 4^(500x500) ... 당연히 시 간 초 과..

보호되어 있는 글입니다.

https://www.acmicpc.net/problem/1890 1890번: 점프 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 www.acmicpc.net 2^63 - 1 흠 ... int로는 커버할 수 없다. 총 경로의 수.. 시간제한 1초.. bfs, dfs로는 시간초과가 난다고 한당.. DP..

보호되어 있는 글입니다.

전에는 DFS로 풀었던거 같은데 , 이번에도 재귀DFS, DP의 방법이 떠올렸다. DP로 풀어보고 싶어서 DP로 풀어봤다. 전의 최적의 값을 이용해서 현재의 최적의 값을 알아낼 수 있기때문에!! 처음의 아이디어는 모두 맞았고 고생을 한 부분은 방문여부에서의 코딩과 반례를 찾는 것이었는데, 대게 DP는 처음의 인덱스와 마지막의 인덱스에서의 예외처리가 핵심인거 같다. N=1일때나 N=마지막인덱스 일때의 상황을 잘 생각해주면 될것 같다. 먼저 DFS로 푼다면, 재귀를 통해 모든 경우를 brute force방법으로 풀어야 겠다고 생각했다. 그 후, DP로 푼다면 점화식이 중요했고 떠오른 점화식은 A[i] = a[i](가능하면) + max{A[i-1].....A[1]} 이었다. 마지막 인덱스가 상담을 못하는 경우..