1575. Count All Possible Routes
도시의 위치와 사용할 수 있는 연료가 주어질 때 start에서 finish로 갈 수 있는 경우의 수를 구하는 문제. 딱 보니 dp 로 간단하게 풀린다. 현재 도시 위치 + 남은 연료로 해서 돌려주면 된다.
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
hard 68
234 233 1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix
자신과 상하좌우 4개 비트를 반전시킬 수 있을 때 모든 비트를 0으로 만드는 최소 횟수를 구하는 문제. 딱 보니 배열 크기도 작고 최소 횟수이므로 BFS로 돌려주면 된다. 하나 까다로운 것은 2차원 리스트를 큐나 방문 set에 넣고 빼고 하는 것인데.. set에 넣기 위해 tuple로 바꾸고...수정하기 위해 리스트로도 바꾸고... 좀 복잡하게 구현하긴 하…
232 943. Find the Shortest Superstring
모든 단어를 substring으로 갖는 가장 짧은 문자열을 구하는 문제. 처음에는 어려운데 비트마스크 DP를 쓰면 된다. 단어들을 뒤로 이어붙인다고 생각하고, 붙인 단어는 visited 처리를 비트마스크로 할 수 있다. 이러면 꽤 풀만한 문제가 된다. suffix 함수는 단어를 뒤로 붙일 때 앞 단어의 중복되는 부분을 제거한 suffix 만 추출하는 함수이…
231 1392. Longest Happy Prefix
접두사와 접미사가 같은 가장 긴 접두사를 출력하는 문제. 딱 보니 그 유명한 KMP 이다. KMP는 현재 인덱스에서 suffix와 같은 prefix의 최대 길이를 구해놓는데, 이를 그대로 사용하면 된다. KMP 는 로이형의 유튜브를 참고하면 이해하기 쉽다.
230 1987. Number of Unique Good Subsequences
배열의 subsequence에서 leading 0는 빼고 만들 수 있는 수의 개수를 구하는 문제. DP이다. 로 두면 이다. 각각 문자를 이전의 결과 뒤에 붙인다고 생각하면 된다. 0은 leading zero 문제 때문에 여기서 더하진 않고 마지막에 0이 있는지만 체크해서 1 더하면 된다 (0 한글자인 경우는 valid 하다) lee 형님의 솔루션도 참고 …
229 1982. Find Array Given Subset Sums
각 부분집합의 합으로 이루어진 배열이 주어질 때 원래의 배열을 찾는 문제. 어려운 문제. 답이 안 떠올라서 코드도 깔끔하고 설명도 괜찮은 디스커션을 참고했다. 아이디어는 다음과 같다. 집합이 있을 때 여기에서 하나의 원소를 골라 이 원소를 포함하거나(including), 포함하지 않는(excluding) 멱집합을 만들 수 있다. 예를 들면 {x, y, z}…
228 1444. Number of Ways of Cutting a Pizza
사과가 올려져 있는 피자가 있을 때 사과가 1개 이상 올라가 있도록 피자를 k개로 나누는 경우의 수를 구하는 문제. 피자는 행 또는 열로 죽 자를 수 있다. 딱 보니 모듈러도 있고 자른 모양이 DP 할 수 있게 생겼다. 점화식을 간단히 만들면 여기까지는 간단한데 사과 개수가 최소 1개 이상 있어야 한다. 입력 크기가 작아서 무식하게 O(nm) 돌면서 사과 …
227 2193. Minimum Number of Moves to Make Palindrome
주어진 문자열에서 최소한의 swap으로 팰린드롬을 만드는 문제. 이런류는 처음에 딱 보면 안떠오른다. 다시 잘 생각해보니 그리디로 될 것 같다. 앞에서부터 탐색하면서 팰린드롬이 되도록 중간에 있는 문자를 뒤로 옮긴다고 보면 된다. 예를 들면 ab....a...b 이런식이라고 하면 맨 앞의 a가 매치되도록 뒤의 a를 맨 뒤로 옮기면 된다. ab ...... …
226 1307. Verbal Arithmetic Puzzle
문자로 이루어진 방정식이 있을 때 문자에 숫자를 적당히 대입해 식이 성립하는지 판단하는 문제. 처음에 간단한 완전탐색 문제인줄 알고 풀었는데 예시부터 시간 초과가 뜸... 생각보다 꽤 빡센 완전탐색 문제. 일단 전체적인 코드는 아래 디스커션 참고함. 먼저 완전 탐색을 돌릴 문자를 구해야 한다. 여기서 맵(카운터)를 쓸 수 있는데 나중에 계산을 빠르게 하기 …
224 1416. Restore The Array
문자열과 k 가 주어진다. k까지의 수를 사용해서 문자열을 나눌 수 있는 경우의 수를 구하는 문제. 딱 보니 간단한 DP 같아서 풀었는데 메모리 초과가 많이 났다... modular 연산을 맨 마지막에 했는데 함수에서 리턴할때 넣어주니 돌아간다... 파이썬이 정수 범위가 없다지만 내부적으론 메모리를 더 쓰기 때문에 메모리가 터졌다 암튼 DP는 간단하다. D…