[백준(baekjoon) 1780] 대회 or 인턴 문제 백준 1780 N x N 크기의 행렬은 -1, 0, 1의 값을 가진다. 다음과 같은 규칙으로 종이를 자른 후, -1, 0, 1로만 채워진 종이의 개수를 차례대로 출력하시오. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. (1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. 해결 알고리즘 전형적인 분할 방식 문제이다. 방법 큰 종이를 9개의 작은 종이로 나누는 과정을 반복한다. 시작점, n을 매개변수로 받아 구하고자 하는 종이의 크기 및 값들에 접근할 수 있다. 3 * 3 for문을 돌린다. 작은 종이의 크기는 n / 3이 될 것이다. 종이의 크기 n == 1까..

[백준(baekjoon) 1080] 행렬 문제 백준 1080 0과 1로만 이루어진 행렬 A, B가 존재한다. 3*3크기의 부분 행렬에 있는 모든 원소를 뒤집는 연산을 이용해 A -> B로 변환하는데 필요한 최소 횟수는? 해결 알고리즘 그리디 알고리즘을 사용해 해결하였다. 값이 변경된 부분을 기준으로 뒤집어 간 후 남은 부분은 동일 여부에 따라 판단하면 된다고 가정하였고, 그 증명이 가능했기 때문. 그리디 알고리즘에 대해 잘 모르신다면 이 글을 참고하세요! 방법 1. A와 B 비교 값을 저장한 check 배열 A와 B의 각 위치를 비교하면 다음과 같은 결론을 낼 수 있다. 값이 같다. : 연산을 거치지 않았거나 짝수 번의 연산을 거쳐 값이 돌아옴. 값이 다르다. : 연산을 홀수 번 거쳐 값이 변경됨. 이를..

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