PS
BOJ 1676 팩토리얼 0의 개수 [Java]
BOJ 1676 팩토리얼 0의 개수 1. 문제 링크 https://www.acmicpc.net/problem/1676 2. 문제 해설 중고등학교 때 배웠던 수학의 기본 내용과 관련된 문제이다. 어떤 숫자 n의 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수는 n을 소인수분해 했을 때 10을 얼마나 가지고 있느냐와 같다. 10을 얼마나 가지고 있느냐는 2 x 5 쌍을 얼마나 가지고 있느냐를 의미한다. 예를 한번 들어보겠다. 240의 경우 소인수분해하면 2^4 x 3 x 5 이다. 2는 4개나 있지만 함께 짝을 맞춰줄 5는 1개 뿐이다. 즉, 2와 5를 모두 가지고 있다면 2와 5의 갯수 중 작은 값이 2 x 5 쌍의 갯수와 같다. 이제 팩토리얼에서 2 x 5 쌍의 갯수를 구하는 것을 어떻게 처리할..
BOJ 1149 RGB거리 [Java]
BOJ 1149 RGB거리 1. 문제 링크 https://www.acmicpc.net/problem/1149 2. 문제 해설 DP문제를 풀 때는 개인적으로 점화식을 세우는 것이 절반 이상이라고 생각한다. 일단 문제를 이해해보자. 문제를 읽어보면 각 집마다 빨강, 초록, 파랑 3가지 색 중 1개를 선택해서 칠할 수 있다. 또 추가적인 조건이 있는데 아래와 같다. - 1번 집의 색은 2번 집의 색과 같지 않아야 한다. - N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. - i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. 복잡하게 쓰여있지만 결국 말하고자하는 바는 이웃한 집과는 색이 달라야한다는 것이다. 구하고자 하는 정답은 위 조건을 만족하면서 모든 집을 칠하..
BOJ 12100 2048 (Easy) [Java]
BOJ 12100 2048(Easy) 1. 문제 링크 https://www.acmicpc.net/problem/12100 2. 문제 해설 5번을 이동시키는데 각 이동마다 4개 방향으로 가지를 뻗쳐나갈 수 있는 백트래킹 문제이다. 문제를 읽어보면 구현해야할 기능은 크게 2가지다. 첫번째는 블록을 이동시키고 합치는 부분이고, 두번째는 백트래킹 과정을 통해 5번을 이동시키면서 모든 상황을 살펴 보는 부분이다. 두 기능을 어떻게 구현할지 생각해보자. 1. 블록을 이동시키고 합치는 기능 - move 메서드 백트래킹 과정에서 매 이동마다 4개의 방향을 선택할 수 있다. 즉, 매 이동마다 4개의 가지를 뻗는다. 그러므로 지금까지의 상황이 담긴 map 배열과, 이동시킬 방향을 인자로 받아야한다. 방향은 동, 서, 남,..
BOJ 1759 암호 만들기 [Java]
BOJ 1759 암호 만들기 1. 문제 링크 https://www.acmicpc.net/problem/1759 2. 문제 해설 백트래킹 문제이다. 다만 조건이 조금 추가되었다. 어떤 조건이 있는지 살펴보자. 1. 암호는 L개의 알파벳 소문자로 구성된다. 2. 최소 한 개의 모음과 두 개의 자음으로 구성된다. 3. 알파벳이 사전 순으로 배열된다. 일단 solve 메서드가 받아야할 인자는 현재 암호의 길이(length), 살펴보고 있는 인덱스(idx), 모음의 수(vowel), 자음의 수(consonant)이다. solve 메서드가 1, 2번 조건을 만족할 때 탈출하여 문제의 조건을 만족시켜준다. 3번째 조건인 암호의 경우의 수가 사전 순으로 배열되게 하기 위해서 입력 받은 arr 배열을 미리 사전 순으로 ..
BOJ 15649 N과 M (1) [Java]
BOJ 15649 N과 M (1) 1. 문제 링크 https://www.acmicpc.net/problem/15649 2. 문제 해설 백트래킹을 할 때는 문제에서 주어진 조건을 잘 살펴야한다. 이 문제에서는 중복 없이 숫자 선택, 사전 순으로 수열 출력 이 2가지 조건만 만족하면 된다. 중복 체크를 하기 위해 vis 배열을 만들어주고, m개의 선택된 숫자를 담을 arr 배열을 만들어준다. 이제 백트래킹 과정을 행할 solve 메서드에 대해 알아보자. 매개 변수로 cnt를 받는데 cnt가 의미하는 바는 선택된 숫자의 갯수이다. 탈출 조건은 cnt가 의미하는 바를 생각하면 자연스레 도출된다. cnt == m 이 되면 solve 메서드를 탈출하고 arr 배열에 저장된 숫자들을 StringBuilder에 담는다..