[백준 / BOJ] 4883 삼각 그래프 (Java)
문제 출처 : https://www.acmicpc.net/problem/4883 4883번: 삼각 그래프 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 그래프의 행의 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N개 줄에는 그래프의 i번째 행에 있는 정점의 비용이 www.acmicpc.net N(N>=2)개의 행, 3개의 열로이루어진 삼각그래프 가있다. 삼각그래프의 각 노드는, (y,x일때) 자신의 위치기준으로 (0, -1) (-1, -1) (-1, 0) (-1, 1)위치에 있는 노드들에서 올수있다. (해당 위치에 노드가 없는경우 올수없다.) 각 노드에 가중치가 있을때, (1,2)위치부터 (N,2)위치까지 가는 최소경로를 구하는 문제다. 풀이 다이나믹 프..
[백준 / BOJ] 2560 짚신벌레
문제 출처 : https://www.acmicpc.net/problem/2560 2560번: 짚신벌레 첫째 줄에 a, b, d, N을 나타내는 네 정수가 빈칸 하나를 사이에 두고 차례로 주어진다. 단, 0<a<b<d≤10,000이고, 1≤N≤1,000,000이다. www.acmicpc.net 한 생물학자가 새로 발견된 짚신벌레에 대해 연구하고있다. 짚신벌레는 1. 태어난지 a일째 되는날부터 새로운 개체를 생성한다. 2. 태어난지 b일째 되는날부터 새로운 개체생성을 중지한다(a일부터 b-1일 까지 개체를 생성함) 3. 태어난지 d일째 되는날 죽는다. 수조안에 짚신벌레가 한마리 있다할때, N일 지난후 살아있는 짚신벌레 개체수를 구하는 문제다. 풀이 완전탐색으로 풀경우, d*d*N = O(N*(d^2))이 되..