아무거나

문제 내용 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 풀이 시간 5분 풀이 과정 DP를 이용한 간단한 풀이 정답 코드 1. 파이썬 import sys sys_input=sys.stdin.readline n=int(sys_input()) arr=[list(map(int,sys_input().rstrip().split())) for _ in range(n)] dp=[[0]*i for i in range(1,n+1)] dp[0][0]=arr[0][0] for i in range(1,n): for j in range(..

백준의 11053과 같은 유형을 흔히 `최장 증가 부분 수열(Longest Increasing Subsequence,LIS)라 하는데 이를 구하는 방법은 크게 두가지가 존재한다. 1. DP를 이용한 풀이 (가장 기본적 간단, 시간복잡도:O(n^2)) 파이썬 import sys sys_input=sys.stdin.readline n=int(sys_input()) arr=list(map(int,sys_input().rstrip().split())) dp=[1] for i in range(1,n): find=0 for j in range(i): if arr[i]>arr[j]: find=max(find,dp[j]) dp.append(find+1) print(max(dp)) 자바 import java.io.*; ..

문제 내용 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 풀이 시간 10분 풀이 과정 DP를 이용해 해결 정답 코드 1. 파이썬 import sys sys_input=sys.stdin.readline n=int(sys_input()) arr=list(map(int,sys_input().rstrip().split())) dp=[1] for i in range(1,n)..

문제 링크 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 시간 25분 풀이 방향성 백트래킹->(시간초과) -> DP->통과 정답 코드 1. 파이썬 import sys sys_input=sys.stdin.readline n=int(sys_input()) arr=[list(map(int,sys_input().rstrip().split())) for _ in range(n)] dp=[[arr[0][0],arr[0][1],..

문제 내용 https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 해결 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 #include //sqrt를 사용하기 위한 header #include #define MAX_N 50001 u..