Debug.Log

백준 10844번 - 쉬운 계단 수문제45656이란 수를 보자.이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오.(0으로 시작하는 수는 없다.) 입력첫째 줄에 N이 주어진다.N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 출력첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. 예제 입력2예제 출력17 접근Dynamic Programming으로 접근한다.첫 째 자리수에 올 수 있는 숫자는 1~9이다.만약 첫 째 자리수가 1이라면, 둘 째자리수는 0 또는 2가 올 수 있다.만약 첫 째 자리 수가 9..

백준 1912번 - 연속합문제n개의 정수로 이루어진 임의의 수열이 주어진다.우리는 이 중 연속된 몇 개의 숫자를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다.단, 숫자는 한 개 이상 선택해야 한다.예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자.여기서 정답은 12+21인 33이 정답이 된다. 입력첫째 줄에 정수 n(1≤n≤100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다.수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. 출력첫째 줄에 답을 출력한다. 예제 입력10 10 -4 3 1 5 6 -35 12 21 -1 예제 출력33 접근Dynamic Programming으로 접근한다.첫 ..

백준 2293 - 동전1문제n가지 종류의 동전이 있다.각각의 동전이 나타내는 가치는 다르다.이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다.그 경우의 수를 구하시오. (각각의 동전은 몇 개라도 사용할 수 있다.) 입력첫째줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000)다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 출력첫째 줄에 경우의 수를 출력한다. 경우의 수는 2^31보다 작다. 예제 입력3 10 1 2 5 예제 출력10 접근Dynamic Programming으로 접근한다.첫 번째 동전만 사용하여 각 k값 마다 가능한 경우의 수를 찾는다.첫 번째~두 번째 동전만 사용하였을 때, 각k 값 마다 가능한 경우의 수를 찾는다.이 때, 첫 번째 동전만 ..

연쇄행렬 최소곱셈 알고리즘 (Matrix Chan Multiplication)연쇄행렬 최소곱셈은 동적 프로그래밍(Dynamic Programming)을 활용하여 연산을 최적화 시키는 것행렬은 결합법칙이 성립한다.(AB)C = A(BC) 그러나 행렬을 곱하는 순서에 따라 곱하는 횟수가 달라진다.예를들어,A : 10x30 행렬B : 30x5 행렬C : 5x60 행렬일 경우(AB)C는 (10x30x5) + (10x5x60) = 1,500 + 3,000 = 4,500번의 연산으로 구할 수 있지만A(BC)는 (30x5x60) + (10x30x60) = 9,000 + 18,000 = 27,000번의 연산을 해야 구할 수 있다. 즉, 연쇄행렬 최소곱셈은 곱하는 순서에 따라 연산의 순서가 달라지는데, 이를 최적화 하는..