yunny.world

  • 홈
  • 태그
  • 방명록

monotone stack 1

[BOJ] 2812번 : 크게 만들기

https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 가장 큰 수를 만들기 위해선 수를 문자열로 보았을 때, 앞쪽 수가 무조건 큰 것이 유리하다. 따라서, 오름차순 모노톤 스택을 관리해 주면 된다. 즉, 스택의 안쪽에 있을수록 큰 숫자가 존재하도록 한다. 구체적으로는, (스택의 top 0) 일때, 스택에서 pop하면서 k를 1씩 감소하면서 관리하면 된다. 숫자를 정확히 k개 지우는 것을 처리하기 위해 다음과 같이 처리해주었다. (k > 0)일때만 스택에서 pop을 하도록 하여, 숫자를 k개..

PS 2022.11.18
1
더보기
프로필사진

안녕하세요 유니월드입니다.

  • 분류 전체보기 (61)
    • PS (25)
    • CP (13)
    • 오류 해결 (1)
    • Python (1)
    • 정리 (6)
      • Data&AI (6)
      • Deep Learning & Computer Vi.. (0)
      • 운영체제 입문 (0)
    • 계획과 후기 (14)

Tag

DP, PS, 그리디, SUAPC, dfs, 가장 가까운 수 찾기, Codeforeces, 구성적, 수학, 이분탐색, monotone stack, Tree, ICPC Sinchon, Digit DP, eulor tour technique, yunny_world, 구현, SieveOfEratosthenes, 맵, randomize algorithm,

최근글과 인기글

  • 최근글
  • 인기글

최근댓글

공지사항

페이스북 트위터 플러그인

  • Facebook
  • Twitter

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.

티스토리툴바