[백준(baekjoon) 1184] 귀농 문제 백준 1184 N x N 크기의 땅은 각 단위 정사각형 (i, j)당 의 수익을 가진다. 이 땅을 변에 평행한 직사각형 땅 두개로 나누고자 한다. 단, 두 땅은 반드시 한 꼭지점에서만 만나고, 총 땅의 수익이 같아야 한다. 조건에 맞게 나눌 수 있는 방법의 수를 출력하라. N = -1,000 해결 알고리즘 배열을 활용한 구현 문제이다. DP를 활용해 풀었다. 방법 생각을 더 깊게할수록 복잡해지는 문제 같다. 다시 처음으로 돌아와서 아래처럼 풀었는데, N의 범위가 작아서 시간초과가 나지 않았다. 중복코드를 줄이기 위해 배열을 활용해 방향키 설정(?)을 해주었다. 1.직사각형이 공유하는 꼭지점이 반드시 하나이다. 즉, 전체 정사각형 땅에서 공유 꼭지점이 될 수 ..

문제 백준 2011 5000자리 이하의 입력 값(숫자)이 주어질 때, 아래와 같은 규칙으로 암호화 할 때, 가능한 문자의 경우의 수는 A : 1, B : 2, … , Z : 26 예시 : 25114를 영어로 바꾸면 ”BEAAD” = {2, 5, 1, 1, 4} “YAAD” = {25, 1, 1, 4} “YAN” = {25, 1, 14} “YKD” = {25, 11, 4} “BEKD” = {2, 5, 11, 4} “BEAN” = {2, 5, 1, 14} 해결 정답률이 낮아서 어려울지 알았지만, DP를 사용하면 생각보다 간단하게 풀린다. 그런데 엄청 틀렸다. 예외처리를 안했기 때문…. 내 생각에 이 문제는 DP가 아니라 예외처리 문제이다…. 예외처리 문제만 읽고 처음엔 0 input이 안 들어오는줄 알았지만..

문제 백준 2225 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하시오 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 한 개의 수를 여러 번 쓸 수도 있다. 해결 결론부터 말하자면 다음과 같은 규칙이다. n = 1 : dp[n][k] = k; k = 1 : dp[n][k] = 1; else : dp[n][k] = dp[n - 1][k] + dp[n][k - 1]; 어떻게? n = 2, k = 3일 경우를 보자. dp[n - 1][k]의 각 케이스 마지막 숫자에 + 1을 해주면 k개의 숫자를 활용해 n을 만들 수 있다. dp[n][k - 1]의 각 케이스에 + 0을 해주면 k개의 숫자를 활용해 n을 만들 수 있다. 알고리즘 DP로 풀었고, bot..

[백준(baekjoon) 2133] 타일 채우기 문제 백준 2133 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. N(1 ≤ N ≤ 30) 해결 알고리즘 DP로 풀었고, bottom-up 방식이랑 top-down 방식으로 각각 풀었다. DP에 대해 아직 잘 모른다면 여기의 알고리즘 부분을 보자. 방법 자세한 설명을 뒤로 하고, 간단하게 핵심만 우선 정리하겠다. N이 홀수일 때 경우의 수는 0이다. width = 2씩 묶어 확인한다. 3 X 2는 3가지 케이스가 나온다. 즉, dp[2] = 3이다. 3 X 2n(n > 1)을 만족하는 케이스는 다음과 같이 나뉜다. 이전에 나오지 않은 특수 케이스 2가지. 3 X 2m(m = 1...n - 1)의 1번 특수 케이스와 dp[2..

[백준(baekjoon) 2579] 계단 오르기 문제 백준 2579 n개의 계단의 각 점수가 주어진다. 다음과 같은 규칙을 따른 최대 점수를 출력하라. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. (예를 들어 1번 계단을 밟으면 1 -> 2, 1 -> 3 중 하나만 택할 수 있다.) 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 해결 i 번째 계단에서 가능한 상황은 다음과 같다. X O O (= 연속 2번 밟은 경우) 이전 계단에서 첫번째로 밟힌 경우에 자신의 점수를 합산한 것 O X O (= 이전은 밟지 않고, 자신이 첫번째로 밟힌 경우) 전전 계단이 밟힌 값 중 큰 점수에 자신의 점수를 합산한 것 O O ..

문제 백준 1912 n(1…100,000)과 n의 크기를 가진 수열이 주어질 때, 연속된 숫자들의 합 중 최대 값을 출력하라. 예시 : {10, -4, 3, 1, 5, 6, -35, 12, 21, -1}일 때, 12+21인 33이 정답이 된다. 해결 간단하게 앞에서 부터 시작해서 각 값으로 끝나는 연속된 수열의 최대 합을 구하면 된다. 자신으로 시작하는 경우 이전 연속 수열에 자신을 포함하는 경우 이렇게 두 가지의 경우로 나눌 수 있으므로, 두 값을 비교해서 큰 값을 저장하면 된다. 시간복잡도는 O(N)이다. 알고리즘 DP로 풀었고, bottom-up 방식이랑 top-down 방식으로 각각 풀었다. DP에 대해 아직 잘 모른다면 여기의 알고리즘 부분을 보자. 구현 java Top-down 방식 1.imp..