www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 이 문제는 DP의 가장 대표적인? 예제 같다. 외우듯이 알아두자 # 1463번 1로 만들기 n = int(input()) dp = [0 for _ in range(n+1)] for i in range(2,n+1): dp[i]=dp[i-1]+1 if i%3 ==0 and dp[i//3]+1

www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 연속합을 스터디때 설명을 약간 들어서 그런지 거기서 얻은 아이디어로 문제를 풀었는데 맨땅에 헤딩식으로 풀었으면 못풀었을 것 같다. DP에서 생명은 점화식을 떠올릴 수 있느냐 없느냐다! (and 항상 저장을 하는 cache 공간이 필요) n = int(input()) arr = list(map(int,input().split())) dp = [0 for _ in range(n+1)] dp[0]=arr[0] for i in ..

www.acmicpc.net/problem/9625 9625번: BABBA 상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했 www.acmicpc.net 풀이1 - 시간초과 문제 읽고 어떤 유형인지 파악안하고 생각나는 대로 풀었다. 제출해보니 시간초과가 나왔고 유형으로 접근해봐야겠다는 생각이 들었다. #9625번 BABBA tmp='A' k= int(input()) for i in range(k): new_tmp='' for j in tmp: if j=='A': new_tmp+='B' elif j=='B': new_tmp+='BA' tmp=new_tmp cnt_A=..

www.acmicpc.net/problem/9507 9507번: Generations of Tribbles 꿍은 군대에서 진짜 할짓이 없다. 그래서 꿍만의 피보나치를 만들어보려고 한다. 기존의 피보나치는 너무 단순해서 꿍은 좀더 복잡한 피보나치를 만들어보고자 한다. 그래서 다음과 같은 피보 www.acmicpc.net 풀이1 - 메모이제이션 없는 재귀 - 시간초과 직관적으로 문제보고 짜봤는데 메모이제이션을 적용하지않아 시간초과 날 것 같았는데 돌려보니 시간초과가 났다 . 재귀 쓸거면 메모이제이션 적용해서 쓰자 t = int(input()) def koong(n): if n

www.acmicpc.net/problem/15641 15641번: SUPER SUPER BINARY SEARCH DELUXE 2.5: THE LEGEND OF THE GOLDEN MAZASSUMNIDA, EPISODE 2: THE MAZWAETL UNIVERSE, PART 2: 1 이상 100 이하의 자연수를 출력한다. 단, 하나의 자연수만 정답이다. 정답은 맞은 사람이 나타날 때마다 바뀐다. 정답보다 작은 수를 출력하면 33% 부근에서 "틀렸습니다"를 받는다. 정답보다 큰 www.acmicpc.net 알고리즘문제는 당연 코드 짜는 문제라고 생각했는데 이문제는 단순 숫자 입력하고 업다운 하는 문제였다 ...ㅎ 1~100 사이 숫자 입력해보고 33% 부근에서 '틀렸습니다'가 뜨면 다운 66%부근에서 '틀..

www.acmicpc.net/problem/3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 이 문제는 이분탐색 문제이다. 이분탐색 공부를 좀 하면서 더 익혀보자 import sys n, m = map(int, sys.stdin.readline().split()) t = [int(sys.stdin.readline()) for _ in range(n)] left = min(t) answer = right = max(t) * m while left = m: right = mid - 1 ans..