Debug.Log

백준 9461번 - 파도반 수열https://www.acmicpc.net/problem/9461 문제오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다.첫 삼각형은 정삼각형으로 변의 길이는 1이다.그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다.나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다.P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.입력첫째 줄에 테스트 케이스의 개수 T가 주어진다.각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100) 출력각 테..

백준 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..

백준 2156번 - 포도주 시식문제효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을..

백준 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번의 연산을 해야 구할 수 있다. 즉, 연쇄행렬 최소곱셈은 곱하는 순서에 따라 연산의 순서가 달라지는데, 이를 최적화 하는..