링크: https://www.acmicpc.net/problem/13976 문제 2133번 문제와 같이 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구하는 문제이지만, N의 범위가 \(10^{18}\) 이다. 풀이 이전에 작성한 2133번 문제의 2번째 풀이 방법과 같지만 그것을 빠르게 계산해야한다. 피보나치 수를 빠르게 구하는 방법과 마찬가지로, 행렬을 이용한 거듭 제곱 트릭을 사용하면 된다. 수열의 값은 같으므로, 편의상 OEIS A001835 수열 \( f(n) = 4 \cdot f(n-1) - f(n-2) \) 을 사용하겠다. 이것을 행렬로 나타내면 아래와 같다. $$\begin{eqnarray} \left( \begin{array}{ccc} f_{n} \\ f_{n-1}..

링크: https://www.acmicpc.net/problem/2133 문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구하는 문제이다. 풀이 3×N 벽을 채우는 경우를 \(f(n)\), 한 칸이 빈 3×N 벽을 채우는 경우를 \(g(n)\) 라고 하자. 왼쪽부터 2×1 또는 1×2 크기의 타일을 하나씩 채워보면서 가능한 경우를 살펴본다. \(g(0)\)와 \(g(2)\)는 타일을 채울 방법이 없으므로 \(g(0) = g(2) = 0\) 이다. 이것을 식으로 나타내면 이렇다. $$f(n) = \begin{cases} 0 & \text{if $n$ < 2} \\ 2g(n-1) + f(n-2) \end{cases}$$ $$g(n) = \begin{cases} 1 & \text{i..

문제 소인수가 2 또는 3 또는 5로만 이루어진 수를 "못생긴 수"라고 했을 때, N번째 못생긴 수를 출력하는 문제이다. New Zealand 1990 Division I에 등장했던 문제로, 여러 저지에서 풀어볼 수 있다. UVa 136 - Ugly Numbers POJ 1338 - Ugly Numbers 정올 1318 - 못생긴 수 풀이 빨간색을 현재까지 살펴본 수, 파란색을 앞으로 살펴볼 수라고 했을 때 그림을 위와 같다. 파란색으로 색칠된 수 중에서 가장 작은 수부터 순서대로 살피면, 그 순서대로 N번째 못생긴 수가 결정된다. 이는 다익스트라 알고리즘에서 그림이 어떻게 그려지는 지를 떠올리면 이해가 쉽다. 수의 중복을 제거하기 위해서 이전에 5를 곱해서 만들어진 수에는 2나 3을 곱하지 않았다. 2..

링크: https://www.acmicpc.net/problem/3640문제가중치가 있는 방향 그래프가 주어지고, 1번 정점에서 V번 정점까지 서로 겹치지 않는 2개의 경로 중 비용이 최소인 경우를 출력하는 문제이다. 겹치지 않는 경로를 찾는 것은 최대 유량으로 해결 가능하고, 그 비용이 최소가 되는 것을 구해야하므로, 네트워크 플로우 유형 중에서 MCMF(Min Cost Max Flow; 최소 비용 최대 유량)인 문제이다. 그래프 문제는 항상 문제 조건을 꼼꼼히 살펴야겠다. 이번에도 "출발과 목적지를 제외하고 같은 중간 지점이나 같은 뱃길을 지나면 안 된다." 에서 정점이 겹쳐서는 안되는 조건을 깜빡해서 계속 틀렸다. 이 조건을 무시하면 틀리는 예외 케이스는 아래와 같다. 최대 유량은 1개이고, 답은 ..

링크: https://www.acmicpc.net/problem/18109 문제 한글 두벌식 자판으로 타이핑할 때, 다음 글자의 초성 자음이 이전 글자의 받침으로 미리 작성되는 경우를 구하는 문제이다.자세한 예시는 문제에 자세히 나와있으니 생략한다. 풀이처음에는 영문 모드로 작성한 아무 문자열이 입력으로 들어오는 줄 알았다.그래서 모든 케이스에 대해 고려하다보니, 오토마타를 그리게 되었는 데 아래와 같다. 나중에 다시 보니 항상 "완성형 한글"이 입력되는 꼴만 입력되더라... (모음 'ㅏ'키인 k 가 대문자 K로 적히는 경우도 없었다)여기서 합성모음은 반모음+반모음(ㅘ, ㅝ)와 둘레모음+반모음(ㅞ, ㅙ) 등을 간략히 표현한 것이다. (알맞은 표현을 알려주시면 감사합니다)화살표에서 겹받침은 ㄳ, ㄼ 등으로..

링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu예전 기억으로는, 삼성 SW 역량 테스트 준비용 샘플 문제가 하나밖에 없었는데 뭔가 많이 추가된 모양이다.이번 문제는 그 중 하나이다.삼성 SW 역량 테스트에는 이런 백트래킹류의 탐색 문제가 자주 나오는 것 같다.문제문제를 요약하자면, 세로 길이가 D이고 가로 길이가 W인 2차원 평면에서, 특정 조건에 맞추기 위해 어떤 행을 모두 A(0) 또는 B(1)로 바꾸는 횟수를 최소로 하고 싶다는 것이다.여기서 조건은, 모든 세로줄에서 같은 종류끼리 K개 이상 연속으로 붙어 있으면 되게 만드는 것이다. 어떤 행을 선택하는 조합이 여러개이므로 ..

링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWK3lS6aF-MDFAWJ문제별표(*) 또는 0~9 숫자가 3개 적힌 카드가 N개 있을 때, 숫자끼리 연결되게 이어 붙여서 그 때의 모든 숫자의 합이 가장 큰 것을 구하는 문제이다. 여기서 별표(*)는 숫자를 연결하지 못하도록 만드는 구분자라고 생각하면 된다. 단순해보이지만 케이스를 제대로 생각못해서 여러번 시도 끝에 맞췄다.풀이는 브루트 포스(Brute force)이다. 먼저 숫자 카드는 아래처럼 6가지의 케이스가 있을 것이다. 편의상 (a) + (b) = 12312* 와 같이 적겠다. 숫자로만 이루어진 (a)는 어디에든 붙을 수 있으니, 그냥 무조건 더해..

링크: https://www.acmicpc.net/problem/5052문제한 문자열이 다른 문자열의 접두어(prefix)이면 NO, 그런 경우가 없으면 YES를 출력하는 문제이다.풀이 1 (정렬)모든 문자열을 사전순으로 정렬하면, 접두어가 겹치는 문자열끼리 붙어있다.어떤 문자열이 직전 문자열의 부분 문자열인지 확인하면 된다.시간 복잡도는 정렬 + 부분 문자열 확인 시간만큼이므로, \(O(nlogn + n|s_{max}|)\)코드 1 (정렬) 풀이 2 (트라이; Trie)분류에 트라이가 있기도 하고, 트라이를 한번도 구현해본 적 없어서 트라이로 풀어봤다.문자열을 하나씩 확인하며 트라이를 만들어간다.어떤 문자열이 끊긴 지점에 "이 곳이 하나의 단어였다"로 리프 표시를 해두고 넘어간다.다음에 트라이를 만드는..