개발하는 동그리

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

[프로그래머스] 42898 : 등굣길 [JAVA] Lv.3 등굣길 보통 이런문제는 상하좌우, 좌표 경우의수 최단거리로 보통 잘 나오는 문제이다.그래서 처음에 보자마자 최단거리의 경우의 수를 찾으려고 했다. 하지만 문제에서 방향은 오른쪽과 아래로만 이동이 가능하다. 즉, 목적지에 도달하기만 한다면 모두 최단거리라는 뜻이다. 이러한 문제는 완전탐색을 할 필요없이 dp를 활용하여 sum누적방식으로 좌표값을 계산하고 최종 마지막 도착지의 인덱스값을 리턴하면 대부분 해결된다. 물론 웅덩이같은 제한조건은 잘 생각하여, 피해갈 수 있도록하고, 범주내에서만 이동할수 있도록 신경써주면 쉽게 풀 수 있다. 문제 풀이 설명 (summary)완전 탐색을 하려고 생각할 수도 있으나, 경우의 수가 너무 커져 시간초과로 실패할 ..

문제 풀이 설명 (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) ..