백준

🔗 문제 링크 9465번: 스티커 💊 문제 요약 스티커가 2행 n열로 주어지며, 각 스티커에는 점수가 있다. 스티커를 한 장 떼었을 때 상하좌우의 스티커는 찢어져 못 쓰게된다. 이러한 조건에서 스티커의 떼었을 때 최대 점수를 알고 싶다. 테스트 케이스의 갯수 T가 주어지며, 각 테스트 케이스 별로 열의 갯수 n과 스티커의 점수가 2줄에 걸쳐 주어진다. 🌿 풀이 설명 처음에는 DFS를 통한 완전탐색으로 문제를 풀려고 했으나, 재귀함수 실행 시 int 매개변수 값이 자꾸 바뀌는 문제가 발생하여 코드가 오답을 뱉어냈다. 결국 정답 코드를 확인하고, DP 문제라는 것을 깨닫게 되었는데 기존에 DFS로 풀어야겠다고 결정하기 전에 DP를 고려하지 않았다는 것을 깨닫게 되었다. 이유는 직전에 풀었던 문제가 DFS 문..

🔗 문제 링크 13549번: 숨바꼭질 3 💊 문제 요약 수빈이는 숨바꼭질 중이다. 자신은 N, 동생은 K에 위치하고 있는 것을 알게 되었다. 수빈이의 위치가 X일 때 걷는다면 1초 뒤에, X+1, X-1로 이동한다. 또는, 순간이동하여 0초 후에 2*X로 이동할 수 있다. 수빈이가 동생에게 가장 빠르게 가는 시간을 구하시오. 🌿 풀이 설명 그리디 문제로 해결하려 했지만, 틀렸습니다 로 인해 문제 유형을 확인하였다. 그래프 이론, 특히 너비 우선 탐색을 사용하여 풀어야 한다는 것을 확인하였다. 응 근데 그래프.? 🫤 내가 알던 그래프는 이런 건데... 지금 문제의 상태는 [{현재 위치}, {시간}] 이면 간선의 가중치를 어떻게 정의해야 하지? 숨바꼭질 3은 간선의 가중치가 변할 수 있는 그래프로 문제를 해..

🔗 문제 링크 1987번: 알파벳 💊 문제 요약 세로 R칸, 가로 C칸인 표 모양의 보드판이 있다. 각 칸에는 알파벳 대문자가 적혀있고, 1행 1열에 말이 놓여있다. 말은 상하좌우 1칸씩 이동이 가능하며, 지금까지 지나오지 않은 알파벳이 적힌 칸으로만 이동할 수 있다. 좌측 상단으로부터 말이 최대 몇 칸 움직일 수 있는지 구하시오. 단, 좌측 상단의 카드도 포함된다. 🌿 풀이 설명 나의 멘탈을 다소 흔들었던 알파벳 문제... 🥹 문제 해결을 위한 의식의 흐름은 이러했다. BFS가 익숙했어서 deque를 사용하여 문제를 해결해보려 한다. → deque에 append하는 형식은 (current_x, current_y, distance, passed_alphbets (set))로 하고, visited도 넣고...

🔗 문제 링크 29714번: 브실이의 구슬 아이스크림 💊 문제 요약 브실이는 요상하게 구슬 아이스크림을 먹는다. 첫 줄에 초기 아이스크림 구슬의 갯수 N이 주어지고, 둘째 줄에 N개의 구슬 숫자들이 공백으로 분리되어 주어진다. 셋째 줄에 입력되는 Q번의 구슬 아이스크림을 먹고 보충하거나, 아무것도 하지 않는 과정을 거쳐 구슬 아이스크림을 먹는다. (정말 요상하다.) Q번 두 개의 줄이 세트로 입력된다. 첫 번째 줄은, 먹으려는 아이스크림 구슬의 갯수와 그 갯수만큼 구슬의 숫자가 주어진다. 두 번째 줄은, 보충하려는 아이스크림 구슬의 갯수와 그 갯수만큼 구슬의 숫자가 주어진다. 만약, 먹으려는 아이스크림 구슬 중, 가지고 있는 아이스크림에 없는 것이 있다면 먹거나 보충하지 않고 넘어간다. 구슬 아이스크림을..

🔗 문제 링크 2734번: 드럼통 쌓기 💊 문제 요약 드럼통을 눕혀서 직사각형 쓰레기통에 쌓으려고 한다. 테스트 케이스의 갯수 T가 주어지며, 각 케이스에서 초기에 놓으려는 드럼통의 갯수 N과 각 드럼통의 x 좌표 N개가 한 줄에 주어진다. 가장 아랫줄을 제외한 모든 줄은 바로 아랫줄의 드럼통 2개와 접하며, 바로 아래 줄보다 하나 적은 드럼통들이 있다. 가장 위에 쌓는 드럼통의 x와 y 좌표를 소수점 넷째자리까지 출력하라. 단, 드럼통 윗면의 반지름은 1이다. 🌿 풀이 설명 정답 코드 더보기 import sys input=sys.stdin.readline T=int(input().rstrip()) for _ in range(T): N, *drums=map(float, input().rstrip().sp..

🔗 문제 링크 1876번: 튕기는 볼링공 💊 문제 요약 지름이 20cm인 볼링공을 폭이 105cm인 볼링 레인에, 레인과 평행한 축을 기준으로 반시계 방향 X도로 레인의 중심에서 던졌다. (10

문제 링크 1916번: 최소비용 구하기 문제 요약 N개의 도시가 있고, 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 각 M개의 버스에 대해 '출발 도시, 도착 도시, 비용'이 주어진다. A 도시에서 B 도시로 가는 최소 비용을 구하자. 도시는 1부터 N까지의 자연수로 나타난다. 풀이 설명 출발 지점부터 도착 지점까지의 최소 비용을 구하는 것, 다익스트라(dijkstra) 알고리즘으로 예시 입출력 문제를 풀어보니, 다른 입력들에서도 답을 구할 수 있으리라 생각되었다. visited를 활용한 다익스트라 구현 어제+그제 문제들을 풀면서 visited 배열을 사용하는 것이 비효율적인 중복 탐색을 방지하여 소요 시간 개선에 탁월하다는 것을 느껴서 오늘 다익스트라 문제도 동일하게 visited ..

문제 링크 14502번: 연구소 문제 요약 연구소에 바이러스가 유출되었다. 바이러스는 벽을 뚫지 못하며 가로 또는 세로 한 칸씩 이동할 수 있다. 벽을 3개 세울 때, 확보할 수 있는 안전 공간의 최대 갯수를 구하고 싶다. 이 때 안전 공간은 벽으로 막혀서 바이러스가 오지 못하는 공간이다. 입력으로 N×M 크기의 연구소가 주어진다. 0은 빈공간, 1은 벽, 2는 바이러스를 의미한다. 풀이 과정 예시의 입출력에서 안전 공간을 최대로 확보할 수 있는 최적의 벽 위치를 컴퓨터가 어떻게 알 수 있을까 생각해본 후, 1) 모든 벽을 세우는 경우에 대해서 2) 안전 공간의 넓이를 계산하고 이의 최대값을 구한다. 라는 접근으로 풀 수밖에 없다고 생각이 들었다. 첫 번째 시도: for문으로 조건에 맞는 경우를 찾아 탐..