문제 백준 10844 n(1…100)이 주어질 때, 길이가 n인 계단 수를 구하는 문제 계단 수 : 인접한 수의 차이가 1인 수 예시 : 12321, 3456, 101 주의 : 0으로 시작하는 수는 없다. 해결 계단 수는 끝자리를 기준으로 하기 때문에, *끝의 자리가 0...9인 경우를 각각 따져보면 된다. N이 100이하이기 때문에, 100 * 10을 해도 1초가 넘지 않으므로 시간초과가 되지 않는다. N = 1의 경우, 0을 제외한 1...9까지가 가능하다. 이 경우는 무조건 초기화 해준다. (N > 1)을 만족하는 길이가 N인 계단 수의 규칙은 다음과 같다. 끝자리가 0 인 계단 수 : 직전 값이 1일 경우에만 가능 끝자리가 9 인 계단 수 : 직전 값이 8일 경우에만 가능 끝자리가 1~8 인 계단..

[백준(baekjoon) 11057] 오르막 수 문제 백준 11057 n이 주어질 때, n개의 자리인 오름차순의 개수를 구하는 문제 예시 : 2232, 1234, 4311 주의 : 인접한 수가 같아도 된다. 해결 오름차순의 조건이 끝의 자리보다 작거나 같은 수이기 때문에, 끝의 자리가 0..9인 개수를 모두 따져보면 된다. 그 결과는 다음과 같다. 해당 표는 int[][] count = new int[n][10]라는 2차원 배열로 나타낼 수 있다. count[n][i]는 n번째에 i로 끝나는 수들의 총 개수이고, count[n][i] = count[n-1][i] + count[n][i-1]라는 규칙을 가지고 있다. 저는 왜 그런지 궁금해하면서 원리를 어떻게든 파악하는 편이라, 여기서 부터 너무 복잡하게 ..

[백준(baekjoon) 11052] 붕어빵 판매하기 문제 백준 11052 n개의 붕어빵이 남았고, 이 중 i개로 이루어진 세트의 가격을 Pi라고 한다. 세트 메뉴의 가격이 주어졌을 때, 최대 수익을 구하는 프로그램을 작성하시오. 예시 n = 4; P1 = 1, P2 = 5, P3 = 6, P4 = 7; ANSWER : P2, P2 = 5 + 5 = 10; 해결 1, 2, 3의 더하기 문제와 흡사하다. n을 이룰 수 있는 조합을 찾아 각각의 Pi를 모두 더한 값 중 최대 값을 찾는 문제이다. 다른 점은 조합이 1, 2, 3만으로 이루어지지 않는다는 것. 결론을 먼저 이야기 한다면, 두 원소의 합이 n이 되는 순서를 고려하지 않은 조합을 찾고, 각 max 가격을 찾아 더하면 된다. ‘두 원소의 합’인 이유..

[백준(baekjoon) 9095] 1, 2, 3 더하기 문제 백준 9095 정수 n이 주어졌을 때, n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 예시 n = 4; 1+1+1+1 / 1+1+2 / 1+2+1 / 2+1+1 / 2+2 / 1+3 / 3+1 input 첫째줄 : T(테스트 개수) 그 다음 줄 부터 : n(11보다 작은 자연수, T번 반복됨) 해결 우리가 찾고자 하는 수는 1, 2, 3의 조합이다. 즉, 쉽게 생각해 1, 2, 3으로 각각 시작하는 경우의 수를 모두 찾아보면 답이 나온다. 예를 들어 n = 6라고 할 때, 1, 2, 3 을 기준으로 생각해 본다면, 6 = 1 + 5, 6 = 2 + 4, 6 = 3 + 3로 나타낼 수 있다. 즉 n = 6의 경우,..

문제 백준 11726 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 주의 할 것은 출력이 10007을 나눈 나머지 라는 것..! (이거 안 읽고 계속 틀렸었다…. 문제는 제대로 읽어야 한다..) 해결 처음에는 width 2인 정사각형이 몇 개가 들어가는 지에 따라 경우의 수를 나누어 보았는데, 결과적으로 더 쉬운 패턴을 발견할 수 있었다…. 1.n = 1 : answer = 1 2.n = 2 : answer = 2 3.n = 3 : answer = 결론적으로, 이러한 점화식 형태를 보인다. 그러니 우린 간단하게 점화식을 풀면 됨..! 알고리즘 DP로 풀었고, bottom-up 방식이랑 top-down 방식으로 각각 풀었다. 모두 알테지만, 다시 한번 간..

문제 백준 1463 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최소값을 출력하시오. 해결 문제가 쉬운 편이지만, 자주 쓰이는 간단한 원리이니만큼 정리를 해보고, memorization 유무에 따른 시간 비교를 해보았다. 알고리즘 BFS 방식으로 해보았다. 트리 구조로 정리하자면 아래와 같다. Queue를 만들어 입력값을 우선 넣는다.(시작점) Queue안의 원소들은 하나씩 pop되어 문제에 정의된 1~3번 과정을 거쳐 Queue에 삽입된다. 일단 가능한 경우의 수를 모두 넣어..