바위 뚫는중

🥈 숨바꼭질https://www.acmicpc.net/problem/1697💡 아이디어BFS라는 것을 알고 풀어서 접근은 간단했다!시작점을 큐에 넣어주기큐에 있는 숫자 개수 만큼 탐색하기각각의 숫자를 +1, -1, *2로 계산하여 범위가 맞으면 큐에 넣어주기🖊️ 풀이# 숨바꼭질from collections import dequeimport sysinput = sys.stdin.readlinen, k = map(int, input().split())q = deque()q.append(n) # 시작점을 큐에 넣어준다visited = [False] * (200001)visited[n] = True # 시작점은 방문처리cnt = 0while q: for _ in range(len(q)): ..

🥇 알파벳 https://www.acmicpc.net/problem/1987 💡 아이디어 처음엔 BFS로 접근해서 풀이했는데, 최대한 깊게! 어디까지 갈 수 있는지를 보는 것이어서 DFS로 바꿨다. 즉 가능한 모든 경로를 탐색하는 문제다. → DFS로 이동가능한 경로를 탐색하고, Backtracking으로 모든! 경로를 확인한다 🧑🏻‍💻 풀이 ⏰ 시간초과코드: set() 사용 #알파벳 골 r, c = map(int, input().split()) arr = [list(input().rstrip()) for _ in range(r)] ans = 0 alp = set() dx = [1,-1,0,0] dy = [0,0,1,-1] def dfs(x, y, count): global ans ans = max(an..

🎒 Knapsack Problem 한 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제 담을 수 있는 물건이 나누어 질 때 → 분할가능 배낭문제 → 그리디 알고리즘으로 해결할 수 있음 담을 수 있는 물건이 나누어질 수 없을 때 → 배낭 문제 🥇 평범한 배낭 문제 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을..

🥇 인구 이동 https://www.acmicpc.net/problem/16234 💡 아이디어 인접한 나라의 국경선을 열지 말지 탐색을 이용해서 구한다 국경선을 열 경우, 연합 배열에 해당 좌표를 넣어준다 열어진 국경선의 총 합을 토대로 각 연합의 인구수 / 연합의 크기를 계산하여 연합 배열에 속한 각 칸의 인구수를 재설정 해준다. 인접한 나라 탐색이 끝날때 마다 날짜를 +1 해준다 📂 풀이 # 인구이동 from collections import deque import sys input = sys.stdin.readline # 인구이동을 위해 인접한 나라를 탐색 def bfs(x,y,l,r): q = deque() q.append([x,y]) dx = [1, -1, 0, 0] dy = [0, 0, 1, ..

🥈2×n 타일링 2 https://www.acmicpc.net/problem/11727 💡아이디어 그림그려보면 규칙 찾는 것은 금방 찾을 수 있었다. 그러나 생각보다 식을 구하는 게 쉽지는 않았던 ,, 전전꺼 * 2 + 전에꺼 = 현재꺼 라는 식을 구해낼 수 있었다! ✒️ 풀이 n = int(input()) dp = [0, 1, 3] if n

🥈 예산 예산 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 54407 20201 14815 36.011% 문제 국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것이다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다. 예를 들어, 전체 국가예산이 485이고 4개 지방의 예..

🥈 A → B 문제 정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다. 2를 곱한다. 1을 수의 가장 오른쪽에 추가한다. A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자. 입력 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. 출력 A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다. 💡 아이디어 코딩테스트에서 많이 본 문젠데, 늘 제대로 잘 못풀었던 기억이 있다 😢 연산의 최솟값이므로 BFS를 이용한다! 비슷한 문제 중에서 최솟값이 아닌 경우 DFS를 이용하는 것도 꽤 있었던 것 같다. B의 값이 완성될 때만 카운트를 출력하고 return해주고, 완성되기 전까지는 B를 초과하지 않는 선에서 *2 혹은 +1의..

🥈 전쟁 - 전투, 실버 1 https://www.acmicpc.net/problem/1303 💡 아이디어 전형적인 탐색문제. N명이 뭉쳐있을땐 N제곱 만큼의 위력을 낸다고 한다. W의 위력 상하좌우 기준으로 상단에 덩어리 9 → 81 하단의 덩어리 7 → 49 130 B의 위력 상단 1 하단에 8 → 64 65 ⚠️ 탐색 알고리즘을 이용해서 W(B)의 갯수를 찾고, 각각의 리스트에 저장하여 제곱한뒤 더하여 return 한다 📝 풀이 # 백준 전쟁 - 전투 from collections import deque # 가로 세로 n, m = map(int, input().split()) war = [] for i in range(m): war.append(list(map(str, input().rstrip()..

🥈점프 💡 아이디어 예제1을 따라 시뮬레이션을 해보자. 0,0 값인 2가 3(4-1)보다 작다면, 2,0 과 0,2로 이동가능하다 2,0(1)과 0,2(3)를 각각 시작값으로 두자 2,0(1) 을 고려해보자. 각각의 x,y가 현재위치 + 좌표값 ≤ 3(4-1) 일 경우만 이동이 가능하다. 이때 3,0 과 2,1이 나온다. 3,0(3) 을 고려해보자. 6,0 3,3 중에서 6은 불가하므로 3,3이 가능하고, 이는 곧 좌표의 맨 아래 끝값이 된다. 대충 정리해보면 x, y 각각의 좌표가 n-1이 될 경우 (끝 값에 도달할 경우) break 후 print 좌표는 현재 좌표값을 기준으로 두가지 갈래로 구해나가고, 움직일 수 있는 길일 경우 전의 좌표를 바탕으로 dp값을 갱신해준다 🧑🏻‍💻 코드 # 백준 점프 n..

🥈 피아노 체조 https://www.acmicpc.net/problem/21318 문제 피아노를 사랑하는 시은이는 매일 아침 피아노 체조를 한다. 시은이는 N개의 악보를 가지고 있으며, 1번부터 N번까지의 번호로 부른다. 각 악보는 1 이상 109 이하의 정수로 표현되는 난이도를 가지고 있다. 난이도를 나타내는 수가 클수록 어려운 악보이다. 1 ≤ x ≤ y ≤ N 을 만족하는 두 정수 x, y를 골라 x번부터 y번까지의 악보를 번호 순서대로 연주하는 것이 피아노 체조이다. 시은이는 피아노 체조를 할 때, 지금 연주하는 악보가 바로 다음에 연주할 악보보다 어렵다면 실수를 한다. 다시 말하자면, i(x ≤ i nl[i]: # 전꺼가 더 크다면 mis[i] = mis[i-1] + 1 # mis[i]는 전의..