전체 글

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net Hint X Solution import sys N=int(sys.stdin.readline()) a=list(map(int,sys.stdin.readline().split())) dy=[1]*N for i in range(1, N): for j in range(0, i): if a[i]>a[j] and dy[i]

www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net Hint x Solution n=int(input()) for i in range(1000000): result=i for j in str(i): result+=int(j) if result==n: print(i) break if i==999999: print(0) 해당 코드는 python 3으로 1828ms로 통과했습니다 1,000,000번 까지라 조금 애매했지만 다행히 통과는 되..

www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net Hint Dynamic Programming은 어떠한 규칙이 있다 해당 규칙을 이용하면 쉽게 답을 작성할 수 있다 필자는 list in list 형식을 이용함 Solution T=int(input()) L=[] for i in range(T): L.append(int(input())) if T==1: print(L[0]) else: L[0]=[L[0],L[0]] L[1]=[L[0][0]+L[1],L[1]] for i in ..

https://www.acmicpc.net/problem/3053 3053번: 택시 기하학 첫째 줄에는 유클리드 기하학에서 반지름이 R인 원의 넓이를, 둘째 줄에는 택시 기하학에서 반지름이 R인 원의 넓이를 출력한다. 정답과의 오차는 0.0001까지 허용한다. www.acmicpc.net Hint 택시 기하학: 한국어 위키 택시 기하학에서는 유클리드 기하학의 원과 다르다 (마름모 모양) Solution 유클리드 기하학에서의 원의 넓이 공식은 반지름 X 반지름 X 원주율(π)이다 그러나 택시 기하학에서는 마름모를 원으로 하므로 넓이 공식은지름 X 지름 X 0.5 이다 import math n=int(input()) print("%.6f"%(math.pi*n*n)) print("%.6f"%(n*n*2)) %..

https://www.acmicpc.net/problem/1065 1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 www.acmicpc.net Hint 두 자리 수는 항상 한수이며 세 자리 수부터 일정한 차이가 있는지 확인한다 Solution List = [] def hans(a): if a < 100: List.append(a) else: hans_list = [] for i in range(len(str(a))-1): hans_list.append(int(str(a)[i+1]) - int(str(a)[i])) hans_list.sort(..

https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net Hint 어떤 경우에 VPS가 안되는지를 파악해보면 된다 Solution T=int(input()) for i in range(T): PS=str(input()) stack=[] for i in range(len(PS)): stack.append(PS[i]) if stack.count(")")>stack.count("("): print("NO") break if i=..