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

[백준(baekjoon) 5525] IOIOI 문제 백준 5525 N+1개의 I와 N개의 O가 교대로 이루어진 문자열 PN = IOIOI...OI (O가 N개)가 있다. 예시 : P1 = IOI, P3 = IOIOIOI I, O로만 이루어진 문자열 S와 N이 주어질 때, S안에 PN이 몇개 들어있는지 구하시오. 해결 알고리즘 정해진 패턴을 찾는 문자열 매칭 알고리즘이라고 할 수있다. PN은 IOI가 N개 만큼 반복되는 형태이기 때문에, KMP와 같은 별도의 알고리즘을 사용하지 않고 for문을 사용해 일일이 IOI패턴을 찾아 횟수를 센 후 N과 비교하는 방식으로 진행하였다. 시간 복잡도 : O(N) 설명 앞서 말한 것처럼 PN은 IOI가 N개 만큼 반복되는 형태이다. 즉, 각 index를 비교해 IOI 패..

[백준(baekjoon) 10769] 행복한지 슬픈지 문제 백준 10769 1.행복한 표정 : :-), 2.슬픈 표정 : :-( 입력 받은 문자열에 두가지 이모티콘이 섞여 들어올 때, 아래 규칙에 따라, 전체적인 분위기를 파악해 결과를 출력하라. 어떤 이모티콘도 포함되어 있지 않음 : none 행복한 이모티콘과 슬픈 이모티콘의 수가 동일하게 포함 : unsure 행복한 이모티콘이 슬픈 이모티콘보다 많이 포함 : happy 슬픈 이모티콘이 행복한 이모티콘보다 많이 포함 : sad 해결 알고리즘 정해진 패턴을 찾는 문자열 매칭 알고리즘이라고 할 수있다. 찾고자 하는 패턴이 모두 다른 3문자이므로 for문을 사용해 일일이 확인하였다. 시간 복잡도 : O(N) 설명 우선 이모티콘 3문자가 연속으로 나오는지 확인..