20210208_코테공부

# 11055 가장 큰 증가 부분 수열 (실버2)

• 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.
• 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.
• 첫째 줄에 수열 A의 합이 가장 큰 증가 부분 수열의 합을 출력한다.

import copy
N, A = int(input()), list(map(int, input().split()))

# DP[i] : i까지 왔을 때, 합의 최대
# 자기 자신이 제일 클 수도 있음 ex) 1000 100 10 1 -> 1000이 젤커
DP = copy.deepcopy(A) 

for i in range(1, N):
    for j in range(i):
        if A[i] > A[j]:
            DP[i] = max(A[i]+DP[j], DP[i])

#마지막이 최대라는 보장없음
#예시ㅣ -> print(DP) [1, 101, 3, 53, 113, 6, 11, 17, 24, 32]
print(max(DP))

 

+ (심화) 합이 가장 큰 증가 부분 수열의 합과 리스트 출력하기 

import copy
N, A = int(input()), list(map(int, input().split()))

# DP[i] : i까지 왔을 때, 합의 최대
# 자기 자신이 제일 클 수도 있음 ex) 1000 100 10 1 -> 1000이 젤커
DP = copy.deepcopy(A)
rev = [i for i in range(N)]
idx = 0

for i in range(1, N):
    for j in range(i):
        if A[i] > A[j] and DP[i] < A[i]+DP[j]:
            DP[i] = A[i]+DP[j]
            rev[i] = j
    if DP[idx] < DP[i]:
        idx = i

print(DP[idx])
while rev[idx] != idx:
    print(A[idx], sep=" ")
    idx = rev[idx]
print(A[idx])

// 결과값
10
1 100 2 50 60 3 5 6 7 8
113
60
50
2
1

 

+ 최장 증가 부분 수열(LIS : Longest Increasing Subsequence)

 

단계별풀기 - 브루트 포스

# 1436 영화감독 숌 (실버 5)

• Point. 1666 2666 3666 4666 5666 6666 이 아니고 6660 6661 6662 6663... 이다.
• 단순 반복문으로 666이 들어있는지 판별한다

n = int(input())
cnt = 0
six_n = 666
while True:
    if '666' in str(six_n):
        cnt += 1
    if cnt == n:
        print(six_n)
        break
    six_n += 1