[2631] 줄 세우기 (최장증가수열, LIS, 2중 for문)

2023. 6. 12. 01:20·Coding Test/DP
728x90
 

2631번: 줄세우기

KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기

www.acmicpc.net

 

 

분석

정렬되어 있는 어린이 빼고 나머지를 이동하므로 LIS의 길이를 구한 뒤 N에서 뺌

 

풀이

import sys
input=sys.stdin.readline

n = int(input())
arr=[]
for _ in range(n):
    arr.append(int(input()))

dp = [0 for _ in range(n)]
for i in range(n):
    dp[i] = 1
    for j in range(i):
        if arr[j] < arr[i]:
            dp[i] = max(dp[i], dp[j] + 1)

# print(dp)
print(n - max(dp))

 

 

 

 

728x90
저작자표시 비영리 변경금지 (새창열림)
'Coding Test/DP' 카테고리의 다른 글
  • [7570] 줄세우기 (연속 최장 증가 수열, LIS)
  • [2631] 줄 세우기 (최장증가수열, LIS, 이분 탐색)
  • [11053] 가장 긴 증가하는 부분수열 (LIS)
  • [2294] 동전 2 (동전 개수 최소값)
Karla Ko
Karla Ko
𝘾𝙤𝙣𝙩𝙞𝙣𝙪𝙤𝙪𝙨𝙡𝙮 𝙄𝙢𝙥𝙧𝙤𝙫𝙞𝙣𝙜, 𝘾𝙤𝙣𝙨𝙩𝙖𝙣𝙩𝙡𝙮 𝘿𝙚𝙫𝙚𝙡𝙤𝙥𝙞𝙣𝙜 𝙔𝙚𝙨!
    250x250
  • Karla Ko
    karlaLog
    Karla Ko
  • 전체
    오늘
    어제
    • Total (467)
      • Spring (19)
      • JPA (4)
      • Cloud & Architecture (15)
        • Kubernetes (5)
        • Docker (3)
        • MSA (2)
        • GCP (1)
        • AWS (4)
      • Devops (1)
      • Message Queue (4)
        • Kafka (2)
        • RabbitMQ (2)
      • Git (4)
      • DB (4)
      • Java (9)
      • Python (4)
      • CS (11)
        • OS (8)
        • Network (2)
        • Algorithm (1)
      • Coding Test (392)
        • programmers (156)
        • Graph (43)
        • DP (37)
        • Search (31)
        • Tree (13)
        • Data Structure (26)
        • Combination (12)
        • Implement (18)
        • Geedy (23)
        • Sort (7)
        • Math (21)
        • geometry (2)
  • 블로그 메뉴

    • 홈
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    Algorithm
    이분탐색
    BFS
    파이썬
    힙
    플로이드워셜
    최단거리
    다익스트라
    알고리즘
    트리
    그리디
    LIS
    덱
    최대공약수
    정렬
    그래프
    큐
    자료구조
    프로그래머스
    DP
    DFS
    월간코드챌린지
    구현
    조합
    재귀
    스택
    동적계획법
    백준
    구간합
    최소신장트리
  • hELLO· Designed By정상우.v4.10.3
Karla Ko
[2631] 줄 세우기 (최장증가수열, LIS, 2중 for문)
상단으로

티스토리툴바