개발하는 동그리

문제 풀이 설명 (summary)전체 모양을 2차 배열모양으로 변경삼각형 모양이 있는 위치를 좌표로 변환홀수, 짝수에 따라 나올 수 있는 경우의 수 구분(DP) 각 인덱스에 나올 수 있는 경우의 수를 누적 마지막 인덱스를 출력 (모든 누적 결과 합) 문제 풀이 접근법정형화된 그리드 경로 문제는 BFS보다 DP가 훨씬 효율적입니다.BFS는 주로 최단거리 혹은 가중치가 있는 경로 탐색에 적합합니다.현재 문제에서는 단순 경로 수 계산 문제이기 때문에, DP 방식이 시간적으로 훨씬 효율적인 것입니다. 풀이 코드 (Code)import java.util.Arrays;public class Main { public static void main(String[] args) { int n = 4; ..

문제 풀이 설명 (summary)완전 탐색을 하려고 생각할 수도 있으나, 경우의 수가 너무 커져 시간초과로 실패할 수 있다.그래서, DP를 활용해서 좌표마다 누적해서 원하는 목적지의 좌표 값을 구한다.또한 (오른쪽, 아래)로만 이동하기 때문에 최단거리로 가는건 고려하지 않아도 된다.목적지에 도착하는 거리는 도착하면 모두 동일하다.  문제 풀이 접근법정형화된 그리드 경로 문제는 BFS보다 DP가 훨씬 효율적입니다.BFS는 주로 최단거리 혹은 가중치가 있는 경로 탐색에 적합합니다.현재 문제에서는 단순 경로 수 계산 문제이기 때문에, DP 방식이 시간적으로 훨씬 효율적인 것입니다. 풀이 코드 (Code)import java.util.ArrayDeque;public class Main { public st..

문제 풀이 설명 (summary)DP (동적 계획법, Dynamic Programming), Bottom-Up 활용피보나치 수열 풀이처럼 접근 문제 풀이 접근법가중치가 있는지 확인 풀이 코드 (Code)import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Main { static int testCase; static int destination; static int[] P; static List shortcuts = new ArrayList(); public static void main(String[] args) ..