BOJ7 [그리디 #17] BOJ 21314 - 민겸 수 https://www.acmicpc.net/problem/21314 21314번: 민겸 수 민겸 수 하나가 주어진다. 민겸 수는 대문자 M과 K로만 이루어진 문자열이며, 길이는 3,000을 넘지 않는다. www.acmicpc.net 접근 방법 두를 최종적으로 계산하는 경우는 두가지 이다. 1. K가 왔을때 2. string이 끝날때 이 두 가지 경우는 최소와 최대 공통적으로 적용된다. 이제 세부적으로 최대와 최소를 구하는 알고리즘을 생각해보자. i) 최대 MKKMMK 의 경우, MK + K + MMK = 50 5 500 이다. K는 50을 곱해버리므로 무조건 M과 붙어야한다. 따라서, 알고리즘은 다음과 같다. 1. M이 왔을 경우, mCnt를 +1 한다. 2. K일 경우, mCnt를 이용하여 수를 계산 .. 2024. 2. 22. [그리디 #15] BOJ 1700 - 멀티탭 스케줄링 https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 1차 시도 너무 간단하게 생각했다. 뒷 부분 중 가장적게 사용되는 것을 뽑는 것으로 진행해버렸다. 당연히 반례가 존재한다. 3 15 3 2 1 2 1 2 1 2 1 3 3 3 3 3 3 위 반례에서 3과 2를 꼽고나서 1이 나왔을 때, 3이 2보다 많이 사용되므로 2를 뽑게된다.. 정답 "가장 나중에 사용되는 것을 우선적으로 뽑자!" 라는 것을 다시 생각해보았다. 나중에 사용된다는 것이 현재 꼽아.. 2024. 2. 16. [그리디 #12] BOJ 20365 - 블로그2 https://www.acmicpc.net/problem/20365 20365번: 블로그2 neighbor 블로그를 운영하는 일우는 매일 아침 풀고 싶은 문제를 미리 정해놓고 글을 올린다. 그리고 매일 밤 각각의 문제에 대하여, 해결한 경우 파란색, 해결하지 못한 경우 빨간색으로 칠한 www.acmicpc.net 1차 시도 예제에 있는 문장을 보고 어그로(?)에 끌려 이상하게 접근을 했다. 하지만, 1~7번 문제를 파란색, 3번을 빨간색, 5번을 빨간색, 8번을 빨간색으로 순서대로 칠한다면 작업 횟수는 4번으로 가장 적다. 위 문장에서 먼저 파란색으로 칠한 다는 것 때문에, 무조건 밑 바탕을 칠하고 가야한다고 생각했다. 따라서, 다음과 같은 알고리즘을 설계함. 1. 가장 많은 색을 바탕으로 깔고 들어간다.. 2024. 2. 13. [그리디 #9] BOJ 11508 - 2+1 세일 https://www.acmicpc.net/problem/11508 11508번: 2+1 세일 KSG 편의점에서는 과일우유, 드링킹요구르트 등의 유제품을 '2+1 세일'하는 행사를 하고 있습니다. KSG 편의점에서 유제품 3개를 한 번에 산다면 그중에서 가장 싼 것은 무료로 지불하고 나머지 두 www.acmicpc.net 접근 방법 3개씩 묶어서 구매할 때, 가장 싼 제품을 무료로 준다는 것이 핵심이다. 금액을 최소로 만들기 위해서는 가장 싼 제품으로 가격이 꽤 나가는 제품이 선정되어야한다. 이를 위해선 나머지 두 제품이 가장 비싼 제품으로 선정되어야 한다는 것이다. 다시 말해, 금액을 내림차순으로 정렬 후, 3개씩 묶어서 구매하면 된다. 정석적인 그리디 접근법으로 다가가면 쉽게 풀 수 있는 문제이다. .. 2024. 2. 11. [👊DP뿌시기 #5] (BOJ 2240) 자두나무 https://www.acmicpc.net/problem/2240 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 문제 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어지는 자두를 받아서 먹고는 한다. 자두를 잡을 때에는 자두가 허공에 있을 때 잡아야 하는데, 이는 자두가 말랑말랑하여 바닥에 떨어지면 못 먹을 정도로 뭉개지기 때문이다. 매 초마다, 두 개의 나무 중 하나의 나무에서 .. 2023. 8. 18. BOJ 1874] 스택 수열 [ 문제 이해 ] 입력 값 예) 3 5 1 2 4 - 1부터 n까지의 수를 순서대로 스택에 넣는다. (+출력) 스택 : 1 2 3 - 위를 하다 입력된 값과 같아지면 그 수를 스택에서 제거한다 (-출력) 스택 : 1 2 (3제거) 스택 : 1 2 4 (5제거) 이런 식으로... - 위 과정을 몇번해서 스택이 비워지고, 해당 수열이 완성되는 지 총 횟수를 출력한다 - 만약 위 과정을 진행하다 수열이 만들어지지 않으면 NO를 출력한다. [ 접근법 ] 1. 스택에 1부터 1씩 증가하면서 스택에 넣는다. 2. 입력받은 값이 스택의 top 과 같아지면 스택을 pop()한다. 3. 1,2 과정을 반복하다 스택이 비워지면 종료 4. 만약 위 과정 중 스택이 입력값이 스택의 topp()보다 크면 "NO" 를 출력하고 .. 2022. 12. 13. 이전 1 2 다음
