문제설명입력 & 출력나의 풀이이번 "백준 - 1로 만들기" 문제는 동적 계획법(DP)을 활용하여 해결할 수 있는 문제입니다. [Algorithm] 동적 계획법(Dynamic Programming, DP, Java) 알아보기동적 계획법 DP란❓ 동적 계획법은 프로그래밍 대회 문제에 가장 자주 출현하는 디자인 패러다임 중 하나로 1940년대 리처드 벨만이 사용하던 용어입니다. 주로 줄여서 DP라고 많이 말하며, 주pixx.tistory.com 이 문제는 주어진 수 n을 1로 만들기 위해 최소 몇 번의 연산이 필요한지를 구하는 문제로, 가능한 연산은 다음과 같습니다n이 3으로 나누어 떨어지면 3으로 나눈다. n이 2로 나누어 떨어지면 2로 나눈다. n에서 1을 뺀다.위 연산을 생각해본다면 결국 3가지의 ..
DP
문제설명입력 & 출력나의 풀이이번 "백준 - 돌 게임"문제는 2명의 플레이어(상근,창영)가 돌을 1개 또는 3개 가져갈 때 마지막 돌을 가져가는 사람이 승자하는 게임입니다. 규칙을 정리하자면 다음과 같습니다.돌이 N개 있다.상근이와 창영이가 번갈아 가며 돌을 가져간다.각 턴에 1개 또는 3개를 가져갈 수 있다.마지막 돌을 가져가는 사람이 승리한다.상근이가 먼저 시작한다.이번 문제는 동적 계획법 (Dynamic Programming)알고리즘을 사용하여 풀 수 있습니다. [Algorithm] 동적 계획법(Dynamic Programming, DP, Java) 알아보기동적 계획법 DP란❓ 동적 계획법은 프로그래밍 대회 문제에 가장 자주 출현하는 디자인 패러다임 중 하나로 1940년대 리처드 벨만이 사용하던 ..
문제설명입력 & 출력나의 풀이 이번 문제는 2xn 타일링 문제에 이어지는 문제입니다. 위 그림과 같은 타일이 존재할 때 입력으로 n을 받아 2xn의 크기의 직사각형을 채우는 문제입니다. 타일을 채우다 보면 n = 5일 때 0~5까지의 타일링의 수는 다음과 같습니다. n= 0 ➡️ 1 (채우는 방법이 없으므로 1부터 시작)n= 1 ➡️ 1n= 2 ➡️ 3n= 3 ➡️ 5n= 4 ➡️ 11n= 5 ➡️ 21위 타일링의 수를 생각해서 DP의 가장 핵심요소인 점화식을 도출해야 합니다. 좀 더 이해를 하기 쉽게 그림으로 표현하면 다음과 같습니다. 만약에 n = 3일 때를 보면 n-1의 타일에서 2x1의 타일이 추가된 것을 볼 수있습니다. n-2의 타일에서 2x2를 채우는 경우는 1x2 ➡️ 2개 2x2 ➡️ 1..
문제설명입력 & 출력 나의 풀이 이번 문제는 가로는 2로 고정되어 있고 입력받은 N의 세로 크기만큼의 직사각형에 2x1, 1x2크기의 타일을 채워 넣을 수 있는 경우의 수를 구하는 문제입니다. 부분 문제의 중복큰 문제를 작은 부분 문제로 나눌 수 있습니다.위 그림처럼 n-1인 직사각형에 2×1 타일을 세로로 놓는 경우와, 크기가 n-2인 직사각형에 1 ×2 타일 두 개를 가로로 놓는 경우로 나눌 수 있습니다. 이렇게 작은 부분 문제들이 중복되어 나타납니다. 최적 부분 구조 DP 문제는 작은 부분 문제의 최적해를 이용해 전체 문제의 최적해를 구할 수 있는 최적 부분 구조를 가집니다.n이 1~5일때 타일을 배치할 수 있는 경우의 수는 위와 같습니다. 그림을 자세히 보면 n일 때는 n-1의 타일에 2x1타일..
