본문 바로가기

백준2

[BOJ/13164] 행복 유치원 (그리디) # 13164 행복 유치원 문제 행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 인접해 있어야 한다. 조별로 인원수가 같을 필요는 없다. 이렇게 나뉘어진 조들은 각자 단체 티셔츠를 맞추려고 한다. 조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다. 최대한 비용을 아끼고 싶어 하는 태양이는 K개의 조에 대해 티셔츠 만드는 비용의 합을 최소로 하고 싶어한다. 태양이를 도와 최소의 비용을 구하자. 문제를 풀게 된 내 흐름을 설명해보겠다. 문제를 먼저 봤을때 제일 먼저 적었던 것은 전체 N명 / 키 순서 => 오름차순.. 2023. 10. 11.

[BOJ/1254] 팰린드롬 만들기 (문자열) 백준 팰린드롬 만들기 문자열 문제 굉장히 간단하다고 생각했는데 풀때마다 뭔가 계속 시간이 걸리고 막힌다. 그래서 내가 겪었던 시행착오들이 재발하지 않기 위해 적어놓고 계속 상기 시켜야겠다. 팰린드롬(Palindrome) 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열 접근방식 1) 중간 기준점 찾기 이렇게 처음부터 접근을 했었는데 도저히 안풀린다. 나처럼 이렇게 시행착오를 겪었던 것 같은 분의 블로그를 보고 아촤차~싶었다. 2) 원본 문자열의 길이만큼 대칭인 경우 abab => abab | abab 3) 문자열 맨 앞글자부터 최대한 적은 글자만큼 대칭 abab => a | bab | a 처음에는 1번으로밖에 생각을 못했는데 2,3번을 보고 나니 내가 완전 잘못 접근하고 있었구나 싶었다. 3번 접근.. 2023. 9. 13.

이전 1 다음

티스토리툴바