개발하는 개구리

🐸 문제 정보 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..

🐸 문제 정보 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 🤖 알고리즘 그리디 ⏱️ 풀이 시간 08.05m 📝 풀이 직전 문제와 같이, 간단한 그리디 문제였다. 처음에 문제 이해를 잘못해서 약간의 시간이 더 소요되었다. 스택을 통해 연속된 0 또는 연속된 1의 개수를 파악한다 연속된 수의 개수가 더 작은 수의 개수를 출력한다. 🧑‍💻 나의 답 # pypy3 import sys input = sys.stdin.readline nums = [0, 0] stack = [] for le in list(map(in..

🐸 문제 정보 2847번: 게임을 만든 동준이 학교에서 그래픽스 수업을 들은 동준이는 수업시간에 들은 내용을 바탕으로 스마트폰 게임을 만들었다. 게임에는 총 N개의 레벨이 있고, 각 레벨을 클리어할 때 마다 점수가 주어진다. 플레이어 www.acmicpc.net 🤖 알고리즘 그리디 ⏱️ 풀이 시간 06.12m 📝 풀이 아주 간단한 그리디 문제였다. 풀이 순서는 아래와 같다. 점수를 뒤에서부터 순회한다. 현재 요소가 직전 요소보다 크거나 같다면, 직전 요소보다 1 작은 수를 대입한다. 이 때 현재 요소의 원래 값과 직전 요소보다 1 작은 수의 차이가 점수를 감소시키는 횟수이며, 이것의 총합이 답이다. 🧑‍💻 나의 답 # pypy3 import sys input = sys.stdin.readline n = ..

🐸 문제 정보 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 🤖 알고리즘 구현 ⏱️ 풀이 시간 60m + 📝 풀이 문제가 난해하고 지문이 불친절해서 진짜 코테를 보는 것 같았다. 인덱스로 접하는 경우가 많은 것 같아, 처음에는 리스트로 풀다가 후에 회전 문제를 고치면서 deque로 바꿨다. 단계를 잘 나누어서 풀어야하는 것 같다. 벨트와 로봇 큐를 시계 방향으로 1만큼 회전 역순 순회하면서 로봇 이동 현재 자리에 로봇이 있어야함 시계 방향 다음 자리에 로봇이 없어야함 시계 방향 다음 자리..

🐸 문제 정보 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 🤖 알고리즘 BFS ⏱️ 풀이 시간 10.06m 📝 풀이 BFS의 정석 같은 문제였다. 딱히 구현이 추가되거나 복잡하게 꼬여있는 것 없이, BFS 이론만 적용해서 풀 수 있는 문제였다. 도달하지 못하는 곳에는 -1을 넣어줘야하는게 복잡해 보일 수 있지만, 오히려 -1로 새로운 지도 배열을 선언해놓고 BFS 돌면서 값을 채워준다면 도달하지 못하는 곳에 자연스럽게 -1이 남게된다. 🧑‍💻 나의 답 # pypy..

🐸 문제 정보 2607번: 비슷한 단어 첫째 줄에는 단어의 개수가 주어지고 둘째 줄부터는 한 줄에 하나씩 단어가 주어진다. 모든 단어는 영문 알파벳 대문자로 이루어져 있다. 단어의 개수는 100개 이하이며, 각 단어의 길이는 10 이 www.acmicpc.net 🤖 알고리즘 구현 ⏱️ 풀이 시간 34.18m 📝 풀이 단순한(?) 구현 문제였다. 일단 모든 문자를 딕셔너리로 처리하며, 단어 안에 해당 문자의 개수를 저장했다. 그리고 첫 번째 단어, 즉 기준이 되는 단어의 길이를 확인하여 기준 점수로 저장했다. 이후 과정은 아래와 같다. 두 번째 단어부터 반복을 돈다. (이 때 임시 점수 변수를 선언한다) 기준이 되는 단어와 같은 단어는 +1, 없거나 다른 단어는 -1을 해준다. 기준 점수와 임시 점수를 비..

🐸 문제 정보 20125번: 쿠키의 신체 측정 쿠키런은 데브시스터즈에서 제작한 모바일 러닝 액션 게임이다. 마녀의 오븐에서 탈출한 쿠키들과 함께 모험을 떠나는 게임으로, 점프와 슬라이드 2가지 버튼만으로 손쉽게 플레이할 수 있는 www.acmicpc.net 🤖 알고리즘 구현 ⏱️ 풀이 시간 23.00m 📝 풀이 처음에 BFS인가 싶었지만, 사실 동서남북 방향으로 이동하는 경우가 없기 때문에 단순한(?) 구현임을 깨달았다. 처음에 머리 위치와 심장 위치를 알게 된다면, 이후 신체 부위의 길이를 측정하는 것은 어렵지 않았다. 각 방향으로 쭉 이동하면서 거리를 재면 되는데, 여기서 단순한 for문을 사용해도 되지만 나는 처음에 BFS인줄 알고 풀던게 있기 때문에 그냥 deque를 사용해서 풀었다. 구현이라 코..