DolphinDash

간단한 dp문제인 줄 알고 덤볐다가 조금 오래걸렸다. 처음엔 def dp(que, target, tries): nq = [] if que[0] > target: return -1 for value in que: if value * 2 == target or value * 10 + 1 == target: return tries+1 else: nq.append(value*2) nq.append(value*10 + 1) return dp(nq, target, tries+1) a, b = map(int, input().split()) print(dp([a], b, 1)) 재귀 함수를 만들어서 돌렸더니 메모리 초과가 났다. 일단 tries 횟수가 높아지면 높아질수록 필요 메모리양이 늘어나고 que[-1]의 메모리..

1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net # 정답코드 import sys sys.stdin.readline def conquest_num(num:int, index:int, C:int)->int: if index == 1: return num % C else: halfindex = index//2 if index % 2 == 0: return conquest_num(num, halfindex, C) ** 2 % C else: return conquest_num(num, halfindex, C) ** 2 * num % C A, B, C = map(int, input()..

5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net 접근 방식에 대해 고민을 하게 만드는 문제. Deque! (덱! 덱이라고! 덱!) 우린 파이썬을 사용하니 문제에 따라 효율적인 방식을 선택할 수 있다. 커서를 움직인다고 생각하더라도 pop(0)일 경우 시간복잡도가 O(n)이기때문에 시간초과가 될 수 있다. 그러므로 우리는 deque로 2개의 큐에다가 나눠 움직이는것처럼 만들어주면 된다. 여기서 deque 2개를 생성하고 문자열에 맞게 함수를 실행해도 되지만 Cursor라는 클래스가 있다고 생각하고 만들면..

9735번: 삼차 방정식 풀기 첫째 줄에 테스트 케이스의 개수 N (0 < N < 100)이 주어진다. 다음 N개 줄에는 삼차 방정식의 계수 A, B, C, D가 한 줄에 하나씩 주어진다. www.acmicpc.net 다항식을 더 쉽게 풀고 싶다면? 조립제법 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 조립제법(組立除法, Synthetic division)이란 다항식을 내림차순으로 정리하여 계수들만 표기하는 간단한 계수들의 조립에서 간단한 곱셈과 덧셈으로만 이루어지는 ko.wikipedia.org ???: 근은 구했는데 어떻게 품? import sys sys.stdin.readline n = int(input()) for i in range(n): A, B, C, D = map(..