개발하는 개구리

🐸 문제 정보 21314번: 민겸 수 민겸 수 하나가 주어진다. 민겸 수는 대문자 M과 K로만 이루어진 문자열이며, 길이는 3,000을 넘지 않는다. www.acmicpc.net 🤖 알고리즘 그리디, 구현 ⏱️ 풀이 시간 12.59m 📝 풀이 예제를 직접 손으로 그려보면 그리디라는 것을 쉽게 파악할 수 있었다. 각각 최대값과 최소값을 찾는 순서는 아래와 같다. 둘다 기본적으로 주어진 입력에 대해 앞에서부터 순회한다. 최대값 M이 나오면 stack에 담는다. K가 나오면 K를 포함한 stack의 길이(n) 만큼 5 * (10 ^ (n - 1))를 문자열로 바꿔 정답 문자열에 더해준다. 마지막에 stack에 담겨진 M을 모두 1로 치환하여 정답 문자열에 더해준다. 최소값 M이 나오면 stack에 담는다. K..

🐸 문제 정보 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 🤖 알고리즘 그리디 ⏱️ 풀이 시간 17.15m 📝 풀이 아주 오래전에.. 2년 전에 풀었던 문제인 것 같다. 알고리즘이 열려있어서 우연찮게 DP라는 걸 봐버렸는데ㅠ 처음에 그리디로 풀려다가 DP로 풀어야하나?! 하고 괜히 고민하느라 더 오래걸렸다. 그냥 그리디로 풀면 쉽게 풀 수 있는 문제였다. 남은 설탕 무게가 5의 배수라면, 5로 나눈 몫만큼 개수 더해주고 반복문 탈출 기본적으로 남은 무게에서 3키로씩 빼주면서 반복 반복문 탈출 후, 남은 무게가 0키로..

🐸 문제 정보 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 🤖 알고리즘 그리디 ⏱️ 풀이 시간 12.49m + a 📝 풀이 골3치고 너무 쉬워서 후딱 풀었는데... 뭔갈 놓친건지 계속 틀리다가 겨우 고쳐서 맞았다ㅠㅠ 풀이자체는 아이디어가 떠오르는대로, 숫자를 하나씩 스택에 넣지만, 앞에 해당 수보다 작은 수가 있다면 k번까지 pop 해주는 식으로 풀었다. 핵심은 이 pop 횟수에 따라 결과 출력이 달라진다는 점이었다. 때문에 k값 자체에 변동을 줘서, k가 0일 경우와 아닐경우를 분리해서 출력했더니 맞았다. 🧑‍💻 나의 답 # pypy3 import sys input = sys.st..

🐸 문제 정보 17615번: 볼 모으기 첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주 www.acmicpc.net 🤖 알고리즘 그리디 ⏱️ 풀이 시간 22.24m 📝 풀이 공을 양 끝으로 옮긴다는 아이디어는 쉽게 얻을 수 있지만, 역시 이를 구현하는 과정이 어려운 문제였다. 한 번 틀리고 검색의 힘을 빌렸음에도 대부분의 블로그에서 아이디어에 대한 이야기만 하고 있을 뿐 공을 옮기는 수에 대한 이야기는 거의 하지 않고 있었다.. 헷갈린다면 아래 방법을 잘 읽어보면 도움이 될 것 같다. 우선 주어진 입력에서 red와 blue의 개수를 찾..

🐸 문제 정보 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 🤖 알고리즘 그리디 ⏱️ 풀이 시간 failed 📝 풀이 dp로 풀다가 도저히 모르겠어서 찾아보니 그리디였다........ 그리디로 푸는 방법은 생각보다 간단했다. 직전 전구만 비교하되, 첫 번째 전구의 경우에는 직전 전구가 없기 때문에 첫번째 전구를 건들지 않고 시작한 경우와 / 첫번째 전구를 건들고 시작한 경우 두개로 나눠서 비교하면 되는 문제였다. 🧑‍💻 나의 답 import sys input = sys.stdin..

🐸 문제 정보 19941번: 햄버거 분배 기다란 벤치 모양의 식탁에 사람들과 햄버거가 아래와 같이 단위 간격으로 놓여 있다. 사람들은 자신의 위치에서 거리가 $K$ 이하인 햄버거를 먹을 수 있다. 햄버거 사람 햄버거 사람 햄버거 사 www.acmicpc.net 🤖 알고리즘 그리디 ⏱️ 풀이 시간 17.29m 📝 풀이 투포인터로 풀어야하는 문제인가..?하고 5분정도 삽질하다가 그리디로 해결했다. 생각보다 시간초과도 안나고 단순하게 풀 수 있는 문제였다. 왼쪽부터 오른쪽으로 탐색 이때 테이블 리스트에는 왼쪽과 오른쪽에 k개 만큼 추가 요소가 있어야 함 2번의 탐색 단계에서 의미 없는 조건문이 필요하지 않도록 현재 인덱스에 'P'가 나온 경우 주변 검색 현재 인덱스부터 좌k 우k 에 'H'가 있다면, 그 'H..

🐸 문제 정보 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 🤖 알고리즘 이분탐색 (이지만 나는 그리디로 풀었..다) ⏱️ 풀이 시간 10.58m 📝 풀이 유형은 이분 탐색이었지만, 문제를 봤을 때 이분탐색보다 그리디가 먼저 떠올랐다. 이분탐색 풀이도 아래에 있다. 입력 값을 오름차순으로 정렬 (현재까지 남은 값 / 남은 인원)과 현재 보고있는 값을 비교한다 만약 현재 보고 있는 값이 더 작다면, 예산 최대 값에서 현재 보고 있는 값을 빼고 res와 뺀 값을 비교한다 반대의 경우, (현재까지 남은 값 ..

🐸 문제 정보 3165번: 5 N과 K가 주어졌을 때, N보다 크면서 5가 적어도 K번 포함되는 가장 작은 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 🤖 알고리즘 그리디 백트래킹 ⏱️ 풀이 시간 60m+ 📝 풀이 사실 완벽하게 풀이하지 못한 문제이다. 질문이 엄청 깔끔하고, 이해하기 쉬운 반면... 정말 엄청나게 틀렸다. 사실 아직까지 틀린 이유를 모르겠다. 기존에 풀이 방식은 아래와 같았다. (num은 n + 1을 리스트로 바꾼 변수, idx는 -1) 백트래킹 함수 내에서 5가 k개 이상이면 멈추도록 함 num[idx]가 5라면 백트래킹 함수를 재귀하는데, idx 값을 -1 해줌 자리수를 넘겨주기 위해서 num[idx]가 5보다 작은 경우, 5로 만들고 idx 값을 -1 하여 재귀..

🐸 문제 정보 6068번: 시간 관리하기 성실한 농부 존은 시간을 효율적으로 관리해야 한다는 걸 깨달았다. 그는 N개의 해야할 일에 (1

🐸 문제 정보 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 🤖 알고리즘 그리디 ⏱️ 풀이 시간 06.23m 📝 풀이 보자마자 그리디 같다고 느껴졌다. 도시를 정방향으로 순회하면서, 주유소 리터 당 값의 최소값을 새로 갱신해준다. 현재까지 나온 리터 당 최소 값을 다음 도시로 이동하는 거리만큼 곱해서 더해준다. 간단한 그리디 문제였다. 🧑‍💻 나의 답 # pypy3 import sys input = sys.stdin.readline INF = sys.maxsize n = int(input().r..