겜돌이의 개발일지

문제 백준 4883 삼각 그래프 C++ 4883번: 삼각 그래프 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 그래프의 행의 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N개 줄에는 그래프의 i번째 행에 있는 정점의 비용이 www.acmicpc.net 풀이 기본적인 DP문제이다. 각 행은 3열이고, 조건에 따라 열까지의 최소 거리를 저장하는 배열 dp에 따라 최소 거리를 갱신해준다. dp 배열의 첫 행 첫 열에는 쓰레기값을 넣어주는데, 시작 지점이 따로 있으므로 첫행첫열에서 최소 거리를 갱신하지 못하게 하기 위함이다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27..

문제 백준 2240 자두나무 C++ 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 풀이 전형적인 dp문제이다. 1번에서 시작한다는 문구를 놓쳐서 디버깅하는데 시간이 쪼오끔 걸렸다... (2번에서도 시작할 수 있는줄 알았음) 움직이지 않는 경우에는 첫번째에 있는 경우이므로, 그 전칸에서 바로 가져오고 1번째 칸은 1번째에서 그대로 내려오거나 / 2번째 칸에서 바꾸거나 2번째 칸은 2번째에서 그대로 내려오거나 / 1번째 칸에서 바꾸거나 각각 2가지 경우가 있으므로 이를 비교하여 더 큰 값을 취하고 dp배열에 저장해두면 ..