TEN BILLION

문제 설명어떤 도시에는 집과 학교가 있고, 학생은 집에서 학교까지 가장 빠른 길로 가려고 한다. 도시의 지도는 m(가로), n(세로) 크기의 격자 형태로 구성되어 있으며, 학생은 항상 오른쪽 또는 아래쪽으로만 이동할 수 있다.그런데 지도에는 물에 잠겨서 지나갈 수 없는 지역들이 있으며, 해당 지역들은 puddles 배열에 좌표로 주어진다.당신은 이 학생이 집 (1, 1)에서 학교 (m, n)까지 갈 수 있는 최단 경로의 개수를 구해야 한다. 단, 경로의 개수가 매우 클 수 있으므로, 정답을 1,000,000,007로 나눈 나머지를 반환해야 한다.입력값m: 격자의 가로 크기 (1 ≤ m ≤ 100)n: 격자의 세로 크기 (1 ≤ n ≤ 100)puddles: 물에 잠긴 지역들의 좌표가 담긴 2차원 배열각 ..

문제 설명숫자 N과 목표 숫자 number가 주어졌을 때, N을 최대 8번만 사용하여 사칙연산(+ - * /)과 숫자 이어 붙이기(N, NN, NNN 등)만으로 number를 만들 수 있는 가장 작은 횟수를 구하는 문제입니다.예: N = 5, number = 12일 때→ 5 + 5 + (5 / 5) = 11은 안 되고,→ 55 / 5 + 2 = 13도 안 되고,→ 5 * 2 + 5 + (5 / 5) = 12 같은 식으로 다양한 조합이 가능합니다.💡 풀이 - DP + Set 활용✅ 핵심 포인트dp[i]는 N을 i번 사용해서 만들 수 있는 모든 숫자 집합입니다.i를 1부터 8까지 순회하며 가능한 연산 조합을 모두 저장합니다.각 단계에서 목표값이 등장하면 바로 i를 리턴합니다.Java 코드import jav..

문제 설명정수 삼각형이 주어졌을 때, 꼭대기부터 바닥까지 이동 가능한 경로 중 숫자의 합이 가장 큰 값을 구하는 문제입니다.삼각형은 다음과 같이 구성되어 있으며, 한 칸 아래 또는 대각선 아래로만 이동할 수 있습니다. [7] [3, 8] [8, 1, 0] [2, 7, 4, 4] [4, 5, 2, 6, 5]​예를 들어 7 → 3 → 8 → 7 → 5 경로의 합은 30입니다. 이처럼 가능한 모든 경로 중 최댓값을 구하는 것이 목적입니다.접근 방식 - Bottom-Up DP이 문제는 동적 계획법(DP) 으로 풀 수 있습니다. 위에서부터 내려오는 방식도 가능하지만, 아래에서 위로 올라가는 Bottom-Up 방식이 훨씬 간단합니다.✅ 핵심 아이디어마지막 줄부터 시작하여, 위로 올라가며 ..

문제 설명주어진 정수 N을 다음 세 가지 연산을 이용해 1로 만들려고 합니다.N이 3으로 나누어떨어지면, 3으로 나눈다.N이 2로 나누어떨어지면, 2로 나눈다.N에서 1을 뺀다.이 연산을 최소한으로 사용하여 1을 만드는 방법을 찾는 문제입니다.해결 방법이 문제는 동적 계획법(DP, Dynamic Programming) 을 활용하여 해결할 수 있습니다.dp[i]를 정수 i를 1로 만드는 최소 연산 횟수라고 정의합니다.dp[1] = 0 (1은 이미 1이므로 연산이 필요 없음)dp[i]는 다음의 세 가지 경우 중 최소값을 선택합니다:dp[i-1] + 1 (1을 빼는 경우)dp[i/2] + 1 (i가 2로 나누어떨어지는 경우)dp[i/3] + 1 (i가 3으로 나누어떨어지는 경우)코드import java.io...