욱이의 IT 생존일지

  • 홈
  • 태그
  • GitHub
  • Linkedin

가장 긴 증가하는 부분 수열 1

[BOJ/2565/Golang] 백준 2565 - 전깃줄

접근 방식 처음에는 점화식을 어떻게 세워야 할 지 매우 고민했습니다. D[i][j] = (i, j)를 연결할 때 삭제 되어야 할 전선의 최소 개수라고도 세워보고, D[i] = i 번째 전깃줄까지 교차줄이 없게하는 최소 삭제 전깃줄의 개수로도 접근해봤습니다. 아무래도 문제가 풀리지 않아, 처음부터 그림을 그려가며, 그 순서를 살펴봤는데요. 어째 보면 볼수록 가장 긴 증가하는 부분 수열의 길이를 구하는 문제와 비슷해보이는 겁니다. 즉, 없애야 하는 전깃줄의 최소 개수를 구한다는 것은, 전체 전깃줄의 개수에서 남아 있어도 되는 전깃줄의 최대 개수를 뺀 값과 일치한다는 것을 발견한 겁니다! 없애야 하는 전깃줄의 최소 개수 = (전체 전깃줄의 개수) - (교차하지 않고 남아 있어도 괜찮은 전깃줄의 최대 개수) 따..

PS/BOJ 2021.05.20
1
더보기
프로필사진

Go언어와 Kubernetes를 좋아하는 엔지니어입니다. 꾸준히 배웁니다.

  • 전체 보기 (162)
    • PS (20)
      • BOJ (20)
    • IT (127)
      • Hadoop (1)
      • Airflow (7)
      • DevOps (6)
      • IT WIKI (25)
      • Network (16)
      • Kubernetes (18)
      • Docker (1)
      • containerd (2)
      • Istio (1)
      • Go (19)
      • OpenSource (1)
      • Python (5)
      • C++ (3)
      • OpenStack (6)
      • OS (10)
      • SQL (1)
      • Coding Tip (4)
    • 욱이야기 (7)
      • 욱이 취업 (1)
      • 욱이 (6)
    • Apple (7)
      • Mac (7)
      • iPhone & iPad & Acc (0)
    • 경제 공부 (1)
      • 부동산 공부 (1)

최근글

인기글

Tag

linux, Go, 고언어, 도커, 고랭, 백준, 컨테이너, 네트워크, Golang, Coding Test, 쿠버네티스, 리눅스, go언어, Network, 고, k8s, Container, Kubernetes, docker, BOJ,

최근댓글

Archives

Calendar

«   2025/05   »
일 월 화 수 목 금 토
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

방문자수Total

  • Today :
  • Yesterday :

Copyright © Kakao Corp. All rights reserved.

  • Wookiist GitHub
  • Wookiist Linkedin

티스토리툴바