https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 스택 문제 이긴 하지만 어떻게 풀어도 O(n^2)의 시간복잡도가 나올 거라는 생각에 for문을 2개 사용해서 문제를 해결하고자 했다..! import sys input = sys.stdin.readline n = int(input()) nge_list = list(map(int, input().split())) answer = [] for i in range(n): for j in range(i,n): if..
https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 폭발 문자열이 있다면 그 문자열은 제거된 상태로 output이 나와야 함 import sys input = sys.stdin.readline word = input() burst = input() stack = [] len_burst = len(burst) for i in word: stack.append(i) if ''.join(stack[-len_burst:]) == burst:..
https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 동전의 종류는 N개이고 각 동전의 개수는 무한개라고 할 때, 가장 적은 동전을 사용하여 가치의 합을 구함 이때, 동전의 개수를 구하기!! 돈으로 나눠주고 나머지를 다음 계산의 입력으로 사용하여 답을 구함 import sys input = sys.stdin.readline n, k = map(int,input().split()) coi..
https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 나의 풀이 2칸씩 이어서 갈 수 있고, 3칸은 안됨 1칸만 띄어서 갈 수 있고 2칸은 안됨 마지막 계단을 무조건 밟아야 함 최대로 나오는 점수를 return 하면 되는 문제이다. dp에는 각 step에서 선택할 수 있는 가장 큰 수가 저장된다. import sys input = sys.stdin.readline n = int(input()) s=[int(input()) for _ in range(n)] pri..
https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 나의 풀이 n개의 정수로만 이루어진 임의의 수열이 있을 때 연속된 몇 개의 수를 선택해서 구할 수 있는 가장 큰 합을 구하려고 한다. [10, 6, 9, 10, 15, 21, -14, 12, 33, 32] t-1 + t의 값이 t보다 크다면 해당 연속된 수열의 합이 가장 큰 것이다.라고 생각하고 문제를 풀었다. import sys n = int(sys.stdin.readline()) nums = list(m..
https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 나의 풀이 다음과 같이 나선 모양의 삼각형이 있다고 할 때, 가장 긴 변의 길이를 K라고 한다. 파도반 수열 P(N)은 나선에 있는 정삼각형의 변(k)의 길이이며 N이 주어졌을 때 p(N)을 구하는 프로그램을 작성하자. 다음과 같이 인덱스가 있다고 하면 p(n)은 p(n-1) + p(n-5)라고 볼 수 있으며 코드로 나타내면 아래와 같다. import sys cnt = int(sys.stdin.read..
https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 나의 풀이 0과 1이 적힌 타일이 있음 0을 00 만 사용 가능하고 1은 단독으로 사용 가능함 N이 주어졌을 때 만들 수 있는 모든 가짓수 1은 1 타일을 하나만 쓰는 경우, 2는 00 타일을 하나만 쓰는 경우로 경우의 수는 1로 같아 피보나치를 구하는 방법과 같은 approach를 가짐 import sys n = int(sys.stdin.readline()) tile_list = [0]*1000000..
https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 나의 풀이 아래의 재귀함수를 효율성 테스트를 통과하게 변경하는 문제 if a 20, then w(a, b, c) returns: w(20, 20, 20) if a < b and b < c, then w(a, b, c) returns: w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) otherwise it returns: w(a-1, b, c) + w(a-1, b-1, ..
