그냥혀유 그냥혀유

전에 풀었던 1,2,3 더하기 업그레이드 버전이다. 같은 수를 중복하지않은 1,2,3 더하기를 만들면된다. 여기서 중복, 감소, 증가라는 단어를 살펴보면 1,1,2,3,4,3,2,1 -> 수를 바로 옆과 비교해서 두개씩 끊어서 생각해보면 된다. 1,1중복 -> 1,2중복x 증가 -> 2,3증가 ->3,4증가->4,3감소 계속 양 옆을 비교하는 것이다. 이제 문제로 돌아가보자. 문제에서는 중복되는 경우의 수를 제거하고 1,2,3을 사용해서 숫자를 만드는 경우의 수를 찾고 싶다. 예시 처럼 4를 만들고자 한다면, 3+1, 1+3,1+2+1의 꼴로 만드는 것이다. 먼저 그냥 1,2,3 더하기 처럼 생각해보자 N이라는 숫자를 만드는 경우의 수는 다음과 같다. N = N-1 +1 N-2 +2 각각 마지막 수까지 ..

구매하려는 카드 N이 주어졌을 때, 카드 N개를 갖기 위해 지불해야하는 금액의 최댓값을 구하는 문제이다. 먼저 문제를 분석해보자. 민규는 카드를 어떻게 구매할 수 있을까? 각 카드팩의 가격이 카드의 갯수와 함께 주어졌다. 카드 1개 p[1] = M원 카드 두개 p[2] = K원 .. 민규가 N개의 카드를 구매한다면, N-1개가 들어있는 카드팩을 구매하고 p[1]개를 구매해서 N개 N-2개가 들어있는 카드팩을 구매하고 p[2]개를 구매해서 N개 0개가 들어있는 카드팩을 구매하고 p[N]개를 구매해서 N개를 구매하는 경우의 수로 나누어 생각해 볼 수 있을 것이다. 우리는 이 중에서 가장 비싸게 카드를 구매하는 방법을 찾으면 된다. 따라서 점화식은 D[n] = MAX(p[i] + D[n-i])일 것이다. 구하..

2*n타일링 문제에서 채울 수 있는 타일 2*2가 추가 된 것이다. 이제 2*2 타일은 2*1과 1*2와 2*2타일로 채울 수 있다. 3가지 타일로 다른 2*n타일로 마찬가지로 n-1타일에 2*1타일 추가 n-2타일에 1*2위아래 추가 n-2타일에 2*2타일 추가의 경우의 수로 2*n타일을 채우는 경우의 수를 생각할 수 있으니 점화식은 D[n] = D[n-1]+D[n-2]+D[n-2]이다. 상태:N , 종료조건 : 0일때는 0 1일때 1개 2일때 3개 return import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static int[] d; public static void main(Stri..

2*N 사이즈의 사각형을 2*1 타일 혹은 1*2타일로 채우는 방법의 경우의 수를 찾는 문제이다. - 먼저 상태와 종료조건을 생각해보자. => 상태 N , 종료조건 : ? 변하지 않는 것: 각 2*N의 타일을 채우는 경우의 수 가령 2*2타일을 채운다면, 2*1 옆으로 두개 1*2위아래로 두개씩 채울 수 있는 경우의 수 2가지 등 2*N의 타일을 채우는 경우의 수를 찾는 과정에서 생기는 2*N-1 ....2*1을 채우는 경우의 수는 변하지 않을 것이다. 이제 큰 문제를 작은 문제로 쪼개서 생각해보자. 2*N타일을 채우는 과정에서 2*n-1 ..2*n-2.. 2*n-3의 타일들을 채우는 경우의 수가 변하지 않는다면, 이를 활용할 수 있을 것이다. 2*N-1타일에서 2*1타일 하나가 추가된 모양이 2*N타일..

정수 N을 1,2,3의 합으로 나타내는 방법의 수를 구하는 문제이다. -먼저 상태와 가장 작은문제를 종료하기 위한 조건을 생각해보자: 상태: N ,종료조건: ? (종료조건 ->더 이상 재귀호출하지않고 이전 호출로 return 시작) 점화식을 만들면서 종료조건을 생각해보자. 문제를 해결하면서 변하지 않는 값 -> 각 수를 만드는 경우의 수 가령 1 => 1개, 2 = 1+1, 2 두개 , 3 = 1+1+1, 1+2, 2+1, 3 4개 등등의 경우의 수는 다른 N을 구하는 과정에서 나오더라도 변하지 않을 것이다. 점화식 N이라는 숫자를 만들기 위해 1,2,3만을 이용해야한다면, N = N-1 +1 = N-2 +2 = N-3 +3 꼴 일 것이다. 예제의 4를 보면 4 = 1+3, 2+2 등으로 표현할 수 있는..

정수 N이 주어졌을 때, 세가지 방법의 연산으로 1로만드는 최소 방법의 수를 구하는 문제이다. 먼저 상태와 가장 작은문제를 종료하기 위한 조건은 직관적이다 --> 상태 :N , 종료조건 N ==1 이제 문제를 풀기위한 점화식을 생각해보자. 먼저, 큰 문제 D[N]을 작은 문제로 쪼개서 생각해보자. (D[N] => N을 만드는 가장 최소의 경우의 수 return) **계산하는 과정에서 변하지 않는것 -> 각 수를 최소방법으로 1로만드는 경우의 수 ex D[2] : 2 ->1 (/2) ,D[3] :3 -> 1 (/3) , D[4] : 4 -> 2 -> 1 (/2) **기억해야할 것 : 각 단계에서 1로만드는 최소의 경우의 수 그렇다면 D[N]을 최소의 경우로 1로만드는 조건은 N을 -> N/3 or N/2 ..

1373 2진법 - 8진법 2진법을 3자리씩 끊어서 읽으면 8진법 public class Main{ public static void main(String[] args) throws Exception { BufferedReader br= new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); Stack s = new Stack(); String input = br.readLine(); //숫자가 너무 커서 자료형에 저장 불가 -->문자로 표현해야함 int size = input.length()%3 == 0 ? input.lengt..

-해결방법 수빈이는 d나 -d로만 움직일 수 있고, 동생들은 자유로운 위치에 있다. 동생이 어떤 위치에 있을 때 D씩 움직여서 잡으려면, 동생은 수빈이와 위치에서 D의 배수만큼 떨어진 자리에 있어야한다. 가령 수빈이가 2에 있고, 동생이 10에 있다면, 수빈이는 2씩 혹은 4씩 움직여야 10에 도달할 수 있다. D가 3이나 5면 수빈이는 절대 10에 갈 수 없을 것이다. 즉 모든 동생들은 수빈이와의 위치와 차이에서 D의 배수만큼의 위치에 있어야 수빈이가 D씩 움직여서 모두 잡을 수 있다. -1. 수빈이와 동생의 위치의 차이를 구한다. -2. 위치의 차이들의 최대공약수를 구한다. public class Main { public static void main(String[] args) throws Excep..