1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 1759. 암호 만들기 접근한 방법 주어진 문자들중 L개의 조합을 구하는 문제입니다. 조합 라이브러리와 DFS를 사용하는 방법이 있는데 저는 DFS를 사용했고 파이썬의 경우 조합 라이브러리를 쓰는 것이 속도 측면에서 더 유리합니다. 먼저 문자들을 정렬해놓고 스택을 이용해서 순서대로 값을 넣어줍니다. L개가 완성되면 자음과 모음 개수를 체크해서 자음이 1개, 모음이 2개 이상인 경우에만 출력해주면 답을 구할 수 있습니다. Python 풀이 import sys input..

6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 6603. 로또 접근한 방법 (1)조합과 (2)DFS를 사용하는 두 가지 방법이 있는데, 범위가 적으므로 Python을 쓰는 경우라면 조합 알고리즘으로 풀어내는게 더 빠르고 효율적입니다. 주어지는 수 들중 6개를 뽑는 경우들을 모두 구하는 것이므로 중복이 없는 조합을 구해야 합니다. 파이썬은 조합 라이브러리가 있지만 자바스크립트는 직접 구현해주어야 하므로 DFS로 풀어내는게 더 유리할 겁니다. DFS를 사용할 경우 스택에 값을 하나씩 넣습니다. 오름차..

1748번: 수 이어 쓰기 1 첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다. www.acmicpc.net 1748. 수 이어쓰기 1 접근한 방법 단순한 유형의 브루트포스 문제입니다. 수의 범위를 보면 최대 1억번입니다. 적당한 시간이 주어진다면 일반적으로 O(n)복잡도로 해결 가능한 범위이지만 이 문제의 경우 제한 시간이 매우 타이트하므로 n번 이내로 해결해야 합니다. 수학적으로 접근합니다. 규칙을 자세히 찾아보면 굳이 일일이 자릿수를 더해줄 필요가 없습니다. 어떤 수의 각 자릿수마다 나올 수 있는 최대 길이는 정해져있습니다. 예를 들면 1개 자리는 1 ~ 9이므로 9번 * 1, 2개 자리는 10~99이므로 90번 * 2, 3개 자리는 100~999이므로 900번 * 3 ... 그러면 ..

2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 2133. 타일 채우기 이 문제는 개인적으로 패턴을 찾아내기까지 시간이 매우 오래걸렸습니다. 6칸짜리 타일까지 일부 만들어보던 중 4칸부터 모든 칸에 2개씩의 족보없는 타일이 들어간다는 것을 알게된 후부터 어느정도 파악하게 되었습니다. 접근한 방법 일단 홀수 칸들은 어떻게 생각해봐도 만들어질 수가 없으니 제외했고, 머리가 좋지않은 저는 일단 4칸까지는 그냥 그려봤습니다. 그려봤을 때 2칸에서 만들어진 3가지 패턴이 이후 패턴에서도 사용되는 것을 볼 수 있었죠. 즉 4칸에서 2칸을 채우는 용도로 보자면 3개의 패턴이 3번씩 채워지는 것을 볼 수 있습니다. 그러면 9가지가 만..

11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 접근한 방법 가장 쉽게 푸는 방법은 가장 긴 증가하는 부분 수열을 구하는 알고리즘을 주어진 수열의 정방향과 역방향으로 적용해주면 해결 가능합니다. 주어진 예제를 봅시다. 1 5 2 1 4 3 4 5 2 1 위 수열에서 정방향으로 가장 긴 증가하는 부분 수열을 DP 테이블에 담았을 때 결과는 아래와 같습니다. 가장 긴 수열이 어떤 부분 수열인지는 상관없습니다. [1, 2, 2, 1, 3, 3, 4, 5, 2, 1] 다음으로 역방향으로 가장 긴 증가하는 부분 수열을 DP 테이블에 담았을..

1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 1149. RGB거리 무작정 1행부터 이전 색깔을 제외하고 가장 작은 값들만 찾아 더해가면 일부 케이스에서 틀리게 됩니다. 각 행마다 나올 수 있는 비용은 총 3가지 이기 때문에 매번 3가지 경우의 비용을 모두 계산해주어야 합니다. 매 행에 들어있는 값을 빨강(R), 초록(G), 파랑(B)이라고 할 때 각 열의 누적 비용은 다음과 같습니다. 현재 행의 R의 누적 비용 = 현재 행의 R의 비용 + 이전 행의 B의 누적 비용과 G의 누적 비용중..