문제 https://leetcode.com/problems/stone-game-ii 풀이 돌이 일렬로 놓여 있고, 현재 M일 때 1개부터 2M개까지 가져갈 수 있다. 돌을 가져간 뒤에는 M이 max(M, 가져간 개수)로 바뀐다. Alice가 항상 먼저 시작하고, Alice가 얻을 수 있는 돌의 최대 개수를 구하면 된다. 현재 차례인 사람이 상대보다 얼마나 더 많이 가져갈 수 있는지로 DP를 정의할 수도 있지만, 이 문제에서는 현재 상태에서 현재 플레이어가 최대로 가져갈 수 있는 돌의 수를 저장하는 방식이 더 직관적이다. dp[i][m]을 i번째 돌부터 시작하고 현재 M이 m일 때, 현재 플레이어가 얻을 수 있는 최대 돌의 수라고 하자. suffix[i]는 i번째 돌부터 끝까지 남은 돌의 합이다. ...
문제 https://leetcode.com/problems/stone-game-iv 풀이 돌이 n개 있고, 매 턴마다 제곱수만큼의 돌을 가져간다. 마지막 돌을 가져가는 사람이 이긴다고 할 때, Alice가 이길 수 있는지 구하면 된다. dp[i]를 돌이 i개 남았을 때 현재 차례인 사람이 이길 수 있는지로 정의한다. 어떤 제곱수 $r^2$을 가져간 뒤 상대 차례의 상태가 패배라면, 현재 플레이어는 그 선택으로 이길 수 있다. 따라서 점화식은 다음과 같다. $$ dp[i] = \text{true} \quad \text{if there exists } r \text{ such that } dp[i - r^2] = \text{false} $$ ...
문제 https://codeforces.com/problemset/problem/1294/C 풀이 테스트 케이스가 t개 존재한다. 먼저, 정수 n이 주어진다. 각 n에 대해 $n = a \times b \times c, \ a, b, c > 1, \ a \neq b, b \neq c, a \neq c$를 만족하는 세 정수 a, b, c가 존재하면 "YES"와 세 수를 출력하고, 그렇지 않으면 "NO"를 출력하면 된다. 인수 분해 문제이다. n이 3개의 정수의 곱으로 표현되어야 하는데, 3개의 정수가 서로소라는 제약조건은 없다. 64처럼 지수가 6이면 $64 = 2^1 \times 2^2 \times 2^3$ 처럼 표현할 수 있기 때문에 인수와 지수 둘 다 중요하다. ...
문제 https://leetcode.com/problems/find-the-lexicographically-smallest-valid-sequence 풀이 word1에서 인덱스를 고르고, 그 문자들로 word2를 만들면 된다. 선택한 문자는 순서를 유지해야 하고, word1의 문자 중 최대 하나는 다른 문자로 바꿔서 사용할 수 있다. 가능한 수열 중 인덱스가 사전순으로 가장 작은 것을 구하면 된다. 앞에서부터 무조건 현재 문자가 같은지 확인하면서 고르면 되지만, 문자가 다른 위치에서 변경 기회를 바로 사용해도 뒤쪽에 남은 문자를 모두 맞출 수 있는지 확인해야 한다. 즉, 현재 위치를 선택했을 때 남은 문자의 개수가 충분해야 한다. ...
문제 https://codeforces.com/problemset/problem/459/B 풀이 n의 원소가 있는 수열 b가 주어진다. b의 원소 두 개를 짝지었을 때, 두 원소의 차이가 가장 클때의 그 차이와, 그 경우의 원소짝의 개수 출력하면 된다. 경우의 수를 구하기 위해 ‘가장 큰 값’을 가진 원소의 개수와 ‘가장 작은 값’을 가진 원소의 개수를 구해야 한다. 가장 큰 값을 가진 원소의 개수를 $maxCount$, 가장 작은 값을 가진 원소의 개수를 $minCount$ 라고 했을 때, 경우의 수는 $maxCount \times minCount$로 어렵지 않게 구할 수 있다. ...
문제 https://codeforces.com/problemset/problem/489/C 풀이 자리수가 m이고 각 자리수의 합이 s인 정수 중 가장 큰 수와 가장 작은 수를 찾는 문제이다. 처음에는 DP로 접근했는데, DP로는 수의 개수 정도만 구할 수 있고, 최대값과 최소값을 찾기는 힘들 것 같았다. 그래서 다시 그리디로 접근했다. 자리수가 m인데 $1 <= m <= 100$ 이기 때문에, int 타입으로 수를 다루는건 쉽지 않고, 배열이나 벡터로 다루는게 더 쉽다. 최대값은 계수가 높은 쪽에 큰 숫자를 배치하고, 최소값은 계수가 낮은 쪽에 큰 숫자를 배치하는 방법을 사용하자. ...
문제 https://leetcode.com/problems/smallest-divisible-digit-product-i 풀이 n보다 큰 수 중에서 각 자리수의 곱이 t로 나눌 수 있는(나머지가 0인 ) 가장 작은 수를 리턴해야 한다. 문제의 제약조건이 $1 <= n <= 100$, $1 <= t <= 10$ 이라서 모든 수를 찾아봐도 된다. 정수의 각 자리수를 모두 곱한 수를 구하는 로직만 구현한 후에, n 부터 시작해서 숫자를 1씩 증가시키면서 t로 나눈 나머지를 구해서 찾으면 된다. 코드 class Solution: def smallestNumber(self, n: int, t: int) -> int: def productDigits(x: int) -> int: product = 1 while x > 0: product *= x % 10 x //= 10 return product answer = n while productDigits(answer) % t != 0: answer += 1 return answer
문제 https://leetcode.com/problems/remove-methods-from-project 풀이 메소드 k에서 시작해서 도달할 수 있는 노드들을 ‘suspicious’ 하다고 했을 때, 이 ‘suspicious’한 메소드들을 k가 직, 간접적으로 호출하는 것을 제외하고도 호출되는 경우가 있는지 확인하고 있다면 전체 메소드를, 없다면 ‘suspicious’한 메소드를 제외하고 리턴하면 된다. 메소드들의 호출 관계가 단방향 엣지 그래프를 이루기 때문에, BFS나 DFS 무엇을 써도 쉽게 k가 직, 간접적으로 호출하는 함수들을 알 수 있다. k에서 시작해서 도달하는 모든 메소드들은 ‘suspicious’ 하기 때문에 방문 여부를 확인하는 배열을 그대로 사용하면 된다. ...
문제 https://codeforces.com/problemset/problem/451/B 풀이 n 크기 수열 a가 주어진다. 이 수열의 특정 구간을 선택해서 뒤집는 것을 1번 했을 때, 이 수열이 오름차순으로 정렬되어 있다면 "yes"와 그 구간을, 불가능하면 "no"를 출력하면 된다. n의 제약 조건이 $1 <= n <= 10^5$ 이기 때문에, 브루트 포스로는 시간 내에 풀기 힘들다. 특정 구간을 선택해서 뒤집는 행동을 1번만 한다는 것이 힌트인데, 구간 하나를 1번 뒤집어서 수열 전체가 오름차순이 된다는 것은, 수열의 일부 구간만 내림차순 이라는 것이다. ...
문제 https://codeforces.com/problemset/problem/580/C 풀이 노드의 값이 1 혹은 0인 트리 그래프와 그 크기인 정수 n이 주어진다. 루트 노드인 1번 노드에서 시작했을 때, 중간에 값이 1인 노드를 연속으로 m번을 초과해서 만날 수 없다. 이 때, 도달할 수 있는 리프 노드의 개수를 출력하면 된다. 트리 전체를 탐색하면서 연속으로 조우한 값이 1인 노드 개수를 관리하면 된다. 그리고 현재 방문한 노드가 리프 노드인지 판정하고, 만약 리프 노드면 1을 더하면 된다. 트리도 그래프이기 때문에, BFS, DFS 어느 쪽이든 가능하지만, 풀이를 할 때 DFS를 사용했다. ...