초이의 끄적끄적

# 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

# 17406 배열 돌리기 4 (골드4)

• 다시 풀어보기
• Point. DFS, 방향벡터, 백트레킹 기법 사용

from copy import deepcopy

N, M, K = map(int, input().split()) # 배열 A크기 N,M, 회전 연산 개수 K
A = [list(map(int,input().split())) for _ in range(N)] # 배열 A 수
Q = [tuple(map(int, input().split())) for _ in range(K)] # 회전 연산 정보
dx,dy = [1,0,-1,0],[0,-1,0,1]   # 방향벡터 남서북동
ans = 10000 # 배열 A의 값의 최솟값

def value(arr): # 행의 최소값
    return min([sum(i) for i in arr])

def convert(arr, qry): # 회전
    (r, c, s) = qry # 중심점 (r,c) 거리 s
    r, c = r-1, c-1 # 좌표가 0,0 시작이기 때문에 -1 해줌
    new_arr = deepcopy(arr)
    for i in range(1, s+1):
        rr, cc = r-i, c+i
        for w in range(4): # 방향 4번 바꿈
            for d in range(i*2): #
                rrr, ccc = rr + dx[w], cc+dy[w]
                new_arr[rrr][ccc] = arr[rr][cc]
                rr, cc = rrr, ccc
    return new_arr

def dfs(arr, qry):
    global ans # 전역변수 설정
    if sum(qry) == K: # 쿼리를 다 처리했을 경우
        ans = min(ans, value(arr)) # 최소값 저장
        return
    for i in range(K):
        if qry[i]:
            continue
        new_arr = convert(arr, Q[i]) # 쿼리 회전
        qry[i] = 1  # 백트래킹 기법
        dfs(new_arr, qry)
        qry[i] = 0

dfs(A,[0 for i in range(K)])
print(ans)

단계별풀기 - 브루트 포스

# 1018 체스판 다시 칠하기(실버5) (참고)

• 크기가 n*m이고, 흰색과 검은색으로 막 칠해져 있는 보드판이 있다.
• 이 보드판을 잘라서 8*8크기의 체스판을 만들려고 한다.
• 체스판은 흰색과 검은색이 번갈아가며 체크무늬를 이루어야한다.
• 보드판을 잘라서, 체스판을 만들기 위해서 알맞게 색을 고쳐서 체크무늬를 만들어야 한다.
• 고쳐야 하는 색의 최소값을 구하라
• Point. 인덱스 합이 짝수인지 홀수인지로 체크무늬를 판단할 수 있다.

n, m = map(int, input().split())
board = list()
mini = list()

for _ in range(n):
    board.append(input())

for a in range(n - 7): # 8*8로 자르기
    for i in range(m - 7):
        idx1 = 0
        idx2 = 0
        for b in range(a, a + 8):
            for j in range(i, i + 8):              # 8X8 범위를 B와 W로 번갈아가면서 검사
                if (j + b)%2 == 0:
                    if board[b][j] != 'W': idx1 += 1
                    if board[b][j] != 'B': idx2 += 1
                else :
                    if board[b][j] != 'B': idx1 += 1
                    if board[b][j] != 'W': idx2 += 1
        mini.append(idx1)                          # W로 시작했을 때 칠해야 할 부분
        mini.append(idx2)                          # B로 시작했을 때 칠해야 할 부분

print(min(mini))

ex) n = 10, m = 13일 경우 len(mini) = (10-7)*(13-7)*2 = 36개 그 값들 중 가장 작은 수 출력

# 1932 정수 삼각형 (실버1)

• 첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.
• Point. 모든 경로를 따지면 2^50 -> 이번생에 못푼다
• DP문제 (다음 상태를 저장하고 사용함)
  1. 상태를 정의한다 
  2. 점화식을 찾는다(구한다) 
  3. 시간복잡도를 계산한다
  4. 코딩한다(재귀 or 반복문 사용)

N = int(input())
# DP[i][j] : i,j 도착했을 때 최대값
# DP[i][j] = max(DP[i-1], DP[i-1][j]) + A[i][j]
A = [[0 for _ in range(N+1)] for i in range(N+1)]
DP = [[0 for _ in range(N+1)] for i in range(N+1)]

for i in range(1, N+1):
    tmp = list(map(int, input().split()))
    for j in range(1, i+1):
        A[i][j] = tmp[j-1]

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

print(max(DP[-1]))

단계별풀기 - 브루트 포스

# 7568 덩치 (실버5)

• 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩치가 각각 (x, y), (p, q)라고 할 때 x > p 그리고 y > q 이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"고 말한다.
• 여러분은 입력에 나열된 사람의 덩치 등수를 구해서 그 순서대로 첫 줄에 출력해야 한다. 단, 각 덩치 등수는 공백문자로 분리되어야 한다.
• point. 정렬 ㄴㄴ, 그냥 자기보다 크고 무거운(둘 다 큰) 사람이 몇 명인지 쟤서 자기 등수만 정하면 된다.

tc = int(input())
student_list = []

for _ in range(tc):
    x, y = map(int, input().split())
    student_list.append((x, y))

for i in student_list:
    rank = 1
    for j in student_list:
        if i[0] < j[0] and i[1] < j[1]:
                rank += 1
    print(rank, end = " ")

# 16768 Mooyo Mooyo (골드4)

• 셀 높이 (1≤N≤100) 및 10 셀 너비
• 각 셀은 비어 있거나 (0으로 표시) 9 가지 색상 중 하나 (문자 1..9로 표시)의 건초입니다. 중력으로 인해 건초 더미가 아래로 떨어 지므로 건초 더미 아래에 0 셀이 없습니다.
• 두 셀이 가로 또는 세로로 직접 인접하고 0이 아닌 동일한 색상을 갖는 경우 동일한 연결된 영역에 속합니다. 최소한으로 연결된 지역이 존재할 때에 K세포, 건초 더미가 모두 사라지고 0으로 변합니다. 이러한 연결된 영역이 동시에 여러 개 있으면 모두 동시에 사라집니다. 그 후 중력으로 인해 건초 더미가 아래로 떨어져 0이 된 결과 K세포 중 일부를 채울 수 있습니다. 결과 구성에서 다시 적어도 크기의 연결된 영역이있을 수 있습니다. K세포. 만약 그렇다면, 그것들도 사라지고 (동시에, 그러한 영역이 여러 개인 경우), 중력은 나머지 세포를 아래쪽으로 당기고, 적어도 크기의 연결된 영역이 없을 때까지 프로세스가 반복됩니다. K에 있다.
• Mooyo Mooyo 보드의 상태를 감안할 때 이러한 작업이 발생한 후 보드의 최종 사진을 출력하십시오.
• point. 함수 나눠서 풀기 / Flood Fill /  dfs사용하기 / 갯수세기, 지우기, 내리기로 나눠서 코드 작성
• 반복해서 풀어보기

def new_array(N):
    return [[False for i in range(10)] for _ in range(N)]

N, K = map(int, input().split())
M = [list(input()) for _ in range(N)]
ck = new_array(N)
ck2 = new_array(N)
dx, dy = [0,1,0,-1], [1,0,-1,0] #방향벡터 설정

def dfs(x,y): # 갯수세기
    ck[x][y] = True # 그룹에 포함되어 있는가
    ret = 1
    for i in range(4): # 4방향 검사
        xx,yy = x+dx[i], y+dy[i]
        if xx<0 or xx>=N or yy<0 or yy>=10: # 구간 내에 있는지 확인
            continue
        if ck[xx][yy] or M[x][y] != M[xx][yy]: # 체크가 되어 있거나 연결이 안되거나
            continue
        ret += dfs(xx,yy)
    return ret

def dfs2(x,y, val): # 지우기
    ck2[x][y] = True # 지워도 되는가
    M[x][y] = '0' # 0으로 바꿔줌
    for i in range(4):
        xx, yy = x + dx[i], y + dy[i]
        if xx < 0 or xx >= N or yy < 0 or yy >= 10:  # 구간 내에 있는지 확인
            continue
        if ck2[xx][yy] or M[xx][yy] != val:
            continue
        dfs2(xx,yy,val)

def down(): #내리기
    for i in range(10): # 세로줄부터 확인하기
        tmp = []
        for j in range(N):
            if M[j][i] != '0': #0이 아닌 수들 저장
                tmp.append(M[j][i])
        for j in range(N-len(tmp)): #0이 아닌 수의 갯수 빼고 0 채우고
            M[j][i] = '0'
        for j in range(N-len(tmp),N): #나머지 수 채워넣기
            M[j][i] = tmp[j- (N -len(tmp))]

while True:
    exist = False
    ck = new_array(N)
    ck2 = new_array(N)
    for i in range(N):
        for j in range(10):
            if M[i][j] == '0' or ck[i][j]: # 0이거나 이미 체크했으면 넘어가기
                continue
            res = dfs(i,j) # 개수 세기
            if res >= K:    # 개수가 K보다 같거나 크면
                dfs2(i,j, M[i][j]) # 지우기
                exist = True
    if not exist:
        break
    down() # 내리기

for i in M:
    print(''.join(i))

단계별풀기 - 브루트 포스

# 2798 블랙잭 (브론즈2)

• N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.

n,m = map(int, input().split())
n_list = list(map(int, input().split()))
sum_list = []
for i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,n):
            nsum = n_list[i] + n_list[j] + n_list[k]
            if nsum <= m:
                sum_list.append(nsum)

print(max(sum_list))

# 2231 분해합 (브론즈2)

• 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.
• 첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다.
• 자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.
• point. 숫자 각자리 더하기 list(map(int, str())) 사용

1) 틀린 답 -> 생성자가 없는 경우 0을 출력해야함을 간과함

n = int(input())
for i in range(1,n+1):
    div_num = list(map(int, str(i)))
    sum_num = i +sum(div_num)
    if sum_num == n:
        print(i)
        break

2) 정답

N = int(input())
print_num = 0
for i in range(1, N+1):
    div_num = list(map(int, str(i)))
    sum_num = i + sum(div_num)
    if(sum_num == N):
        print_num = i
        break
print(print_num)