문제 21735 - 눈덩이 굴리기 접근 m이 작아서 완전 탐색으로 풀었다. 0번째 칸에서 시작해서 한 턴에 한칸, 혹은 두 칸을 가는 경우에 대해 m번 째 턴까지 모든 경우를 확인했다. 코드 파이썬 코드 def bf(arr, idx, m, cnt, nowSize, flag): if idx >= len(arr): ...

문제 19941 - 햄버거 분배 접근 그리디 알고리즘이다. 앞에서부터 차례대로 보면서 해결하면 된다. 나는 사람을 기준으로 해결했다. 우선 입력받은 값에서 햄버거와 사람을 나누어 담아준다. 인덱스를 기준으로 담아주면 된다. 그 후 앞에서부터 사람을 한명 선택하고, 왼쪽에서부터 햄버거를 확인한다. 햄버거를 하나 꺼내서 거리를 비교해보고...

문제 18870 - 좌표 압축 접근 list, set, dict를 모두 사용했다. 우선 입력받은 배열을 set으로 바꿔 중복을 없애준 후, 다시 list로 바꿔서 정렬한다. 해당 리스트를 이용해 딕셔너리를 구성하는데, key는 요소의 값, value는 요소의 인덱스로 한다. 이러면 특정 i가 배열에서 몇 번째로 작은 수인지 바로 확인할 수...

문제 5430 - AC 접근 문제 자체보다 입출력 처리가 더 까다로웠다.. 문제는 거꾸로 뒤집는다고 진짜로 배열을 뒤집고 있으면 안된다. 아마 100% 시간초과가 뜰 것이다. D일 때 앞에서만 뺀다고 했다. 거꾸로 뒤집는다는 것은 뒤에서 빼겠다는 말과 동일하다. 결국 덱으로 구성해주고 R의 횟수에 따라 앞에서 뺄지 뒤에서 뺄지를 정해주면...

문제 10816 - 숫자 카드 2 접근 n과 m이 제법 큰 수이다. 그냥 배열을 두고 하나씩 탐색한다면, 총 O(nm)이 걸린다. 아마 통과하기 힘들어보인다. 이 문제는 해시를 사용해야 한다. 파이썬은 훌륭한 딕셔너리가 있으니 사용해주자. key에는 숫자가 들어오고, value에 해당 숫자가 몇 번 나왔는지 카운트해준다. 코드 ...

문제 11399 - ATM 접근 그리디 문제이다. i 위치에 있는 사람은 항상 i-1번째 위치까지의 시간의 총합만큼 기다려야 한다. 때문에 걸리는 시간이 적을 수록 앞에 서는게 좋다. 전체 배열을 정렬해주고, 앞에서부터 차례로 걸리는 시간을 연산해주면 된다. 코드 파이썬 코드 n = int(input()) arr = list...

문제 3085 - 사탕 게임 접근 생각보다 복잡하다고 느꼈다. 특정 인덱스 (i, j)가 주어졌을 때, (i, j)에서 가로, 세로를 각각 검사한다. 가장 긴 공통 문자열의 길이를 반환한다. 이 것을 반복해줘야 하는데, 생각보다 검사해야될 부분이 많아서 꼼꼼하게 생각해야한다. 우선 특정 위치의 두 개를 변경했을 때 전체 판을 다 검사하는...

문제 2231 - 분해합 접근 어떤 수의 생성자 중 최소값을 찾아야 한다. 최소값을 찾기 위해 1부터 모두 확인해봐야 할까? 가능은 하겠지만 비효율적일 것 같다. 예를 들어, 1000000의 생성자를 찾는데 굳이 1부터 확인해야 할까? 그럼 생성자를 찾을 때 어디서부터 찾기 시작해야 할까? 분해합을 만들기 위해선 결국 생성자 자신과 자신의...

문제 1699 - 제곱수의 합 접근 DP 문제이다. 동전의 개수 x 구하고자 하는 K만큼의 배열을 할당해준다. DP(i, j) = i번째 동전까지를 사용했을 때, j원을 만드는 동전의 최소 개수이다. DP는 처음에 큰 값(나의 경우는 inf를 이용)으로 초기화해준다. 동전의 가장 작은 단위가 1원이 아닐 수도 있다. 동전을 정렬한 후...

문제 동굴 탐험 접근 호율성 테스트를 통과하기 힘들었다. 처음에 기본 골격은 BFS로 잡고 시작했다. 효율성 맞추려고 하다보니 BFS랑 DFS랑 조금 짬뽕된 느낌.. 인접 리스트로 그래프를 표현해준 후, pre_visit라고 해서 선행해야 하는 노드들을 담아주었다. 0번 노드에 선행노드가 필요하다면 시작도 못하므로, 항상 False이다...