개발하는 개구리

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

🐸 문제 정보 22868번: 산책 (small) 코로나로 인하여 확찐자가 되버려 오늘부터 산책을 하려고 한다. 이를 위해 산책할 경로를 정하려고 한다. 현재 있는 곳 $S$에서 출발하여 $S$와 다른 곳인 $E$를 찍고 다시 $S$로 돌아오는 경로로 www.acmicpc.net 🤖 알고리즘 이분탐색 ⏱️ 풀이 시간 26.22m 📝 풀이 문제를 보고 이분탐색으로 풀어야된다는 것은 알았으나... 정확한 아이디어가 떠오르지 않아 검색의 힘을 빌렸다. 처음에는 mid와 근사한 값에 공유기를 위치시키는 형태로 이분탐색을 생각했었는데, 그게 아니라 mid는 두 집 사이의 거리로 두고, 그 거리만큼 공유기를 두었을 때 비치할 수 있는 공유기의 개수로 정답을 파악하는 형식이었다. 이때 start와 end의 값을 평소처..

🐸 문제 정보 7511번: 소셜 네트워킹 어플리케이션 각 테스트 케이스마다 "Scenario i:"를 출력한다. i는 테스트 케이스 번호이며, 1부터 시작한다. 그 다음, 각각의 쌍마다 두 사람을 연결하는 경로가 있으면 1, 없으면 0을 출력한다. 각 테스트 케이스 www.acmicpc.net 🤖 알고리즘 유니온 파인드 ⏱️ 풀이 시간 16.43m 📝 풀이 유니온 파인드의 정석같은 문제였다. 그래프가 연결되어있는지 찾아야하는데, 시간이 조금 걸렸던 이유는 마지막에 parent[a]와 parent[b]를 비교했다.. find(a)와 find(b)로 고쳐서 통과할 수 있었다. 🧑‍💻 나의 답 # pypy3 import sys input = sys.stdin.readline def find(x): if par..

🐸 문제 정보 17485번: 진우의 달 여행 (Large) 첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2 ≤ N, M ≤ 1000)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다. www.acmicpc.net 🤖 알고리즘 DP ⏱️ 풀이 시간 35.48m (failed) 📝 풀이 DP는 어렵다... 점화식이 안떠올라서 결국 검색으로 아이디어를 얻었다. 3차원 DP 리스트 선언 [row][col][직전 방향] 현재 방향과 다른 방향의 직전 요소들 중, 최솟값을 현재 요소와 더해줌 이 때, 각 행의 0번째 열과 마지막 열의 경우, 직전 방향에 유의해야함 0번째 열은 직전 ↘ 방향이 없다 마지막 열은 직전 ↙ 방향이 없다..

🐸 문제 정보 2503번: 숫자 야구 첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트 www.acmicpc.net 🤖 알고리즘 구현 ⏱️ 풀이 시간 15.14m 📝 풀이 처음에 숫자 야구 규칙을 직접 코드로 구현해야하나..? 하고 헉 했는데, 알고보니 그냥 순열에서 조건 맞지 않는 요소를 제거하는 문제였다. 파이썬이니까 permutation 쓰고, set으로 시간복잡도를 조금이라도 줄이고자 했다. 🧑‍💻 나의 답 # pypy3 import sys from itertools import permutations input = sys.stdin.readline n ..

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

🐸 문제 정보 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 🤖 알고리즘 백트래킹 ⏱️ 풀이 시간 24.36m 📝 풀이 간단한 백트래킹 문제인데도, 재귀 내부 로직이 잘 안떠올라서 정답을 참고했다ㅠㅠ 임의의 수열을 만드는 재귀 함수인데, 다 풀고나니 그냥 permutation 써도 됐겠다는 생각이 들었다. 🧑‍💻 나의 답 # pypy3 import sys input = sys.stdin.readline n = int(input().rstrip()) nums = list(map(int, input().rstrip().spli..

🐸 문제 정보 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 🤖 알고리즘 유니온파인드 ⏱️ 풀이 시간 failed 📝 풀이 너무 오랜만에 유니온 파인드라 결국 예전에 작성해뒀던 아카이브를 찾아봤다ㅠㅠ 예전 벨로그에서 작성했던 유니온 파인드 관련 글이다. velog velog.io 유니온 파인드로 각 노드 별 연결 여부를 찾아내면 나머지는 쉽게 풀 수 있었다. 🧑‍💻 나의 답 # pypy3 import sys input = sys.stdin.readline def find(x): if parent[x] != ..

🐸 문제 정보 16938번: 캠프 준비 난이도가 10, 30인 문제를 고르거나, 20, 30인 문제를 고르면 된다. www.acmicpc.net 🤖 알고리즘 백트래킹 ⏱️ 풀이 시간 12.43m 📝 풀이 시간복잡도 무조건 터질거라고 생각했는데 바로 성공해서 읭 한 문제였다. 문제 수가 15개 밖에 안되니까, 문제 내용대로 직관적인 백트래킹 함수를 작성했다. (현재 인덱스, 현재까지의 합, 최소, 최대)를 인자로 전달하는 백트래킹 함수 합이 L과 R 사이이고, 최대 - 최소가 X보다 크거나 같다면 res 갱신 🧑‍💻 나의 답 # pypy3 import sys input = sys.stdin.readline n, l, r, x = list(map(int, input().rstrip().split())) a ..

🐸 문제 정보 20208번: 진우의 민트초코우유 첫번째 줄에 민초마을의 크기인 N과 진우의 초기체력 M, 그리고 민트초코우유를 마실때 마다 증가하는 체력의 양 H가 공백을 두고 주어진다. N, M, H는 모두 10보다 작거나 같은 자연수이다. 두번째 www.acmicpc.net 🤖 알고리즘 백트래킹 ⏱️ 풀이 시간 32.00m 📝 풀이 처음에 2차원 리스트 보이자마자 BFS로 풀었다가 메모리 터지고... 백트래킹으로 풀어야한다는 것을 알게됐다. 이런 2차원 리스트 주어졌을 때 그냥 생각 안하고 BFS로 푸는 습관좀 고쳐야겠다. 백트래킹으로 푸는 경우 풀이는 아래와 같다. 집의 인덱스와, 민트초코 우유가 있는 인덱스 모두를 찾기 집의 인덱스부터 시작해서, 민트초코 우유의 인덱스로 하나씩 이동해보기 이때, ..