바위 뚫는중

🥈 피아노 체조 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]는 전의..

🥈 등수 매기기 https://www.acmicpc.net/problem/2012 문제 2007년 KOI에 N명의 학생들이 참가하였다. 경시일 전날인 예비소집일에, 모든 학생들은 자신이 N명 중에서 몇 등을 할 것인지 예상 등수를 적어서 제출하도록 하였다. KOI 담당조교로 참가한 김진영 조교는 실수로 모든 학생의 프로그램을 날려 버렸다. 1등부터 N등까지 동석차 없이 등수를 매겨야 하는 김 조교는, 어쩔 수 없이 각 사람이 제출한 예상 등수를 바탕으로 임의로 등수를 매기기로 했다. 자신의 등수를 A등으로 예상하였는데 실제 등수가 B등이 될 경우, 이 사람의 불만도는 A와 B의 차이 (|A - B|)로 수치화할 수 있다. 당신은 N명의 사람들의 불만도의 총 합을 최소로 하면서, 학생들의 등수를 매기려고 ..

2️⃣ 장애물 인식 프로그램 https://softeer.ai/practice/6282 💡 아이디어 DFS로 1을 발견하고, 상하좌우로 탐색하여 1을 또 발견하면 계속해서 카운트를 해주고, 상하좌우로 발견이 안되면 관둔다 각각의 구간별로 카운트를 해줘야하는데 이때 배열을 따로만들어서 길이를 세어주고, 초기화해주는 방식으로 풀이했다. 첨엔 숫자로 두고 했는데 자꾸 에러가 나서 구글링의 도움을 받았다. ✍🏻 풀이 n = int(input()) block = [] for i in range(n): block.append(list(map(int, input()))) def dfs(x,y): if x = n or y = n: return False if block[x][y] =..

2️⃣ 지도 자동 구축https://softeer.ai/practice/6280💡아이디어 공식세우고 대입해주면 되는 문제이다!아주 간단한 문제였는데, 내 생각보단 매우 오래걸렸다..크흠..📝 풀이import sysN = int(input())mac = [0] * 16mac[0] = 2for i in range(1, N+1): mac[i] = mac[i-1] + (2**(i-1)) print(mac[N]**2)

2️⃣ 금고털이 https://softeer.ai/practice/6288 루팡은 배낭을 하나 메고 은행금고에 들어왔다. 금고 안에는 값비싼 금, 은, 백금 등의 귀금속 덩어리가 잔뜩 들어있다. 배낭은 W ㎏까지 담을 수 있다. 각 금속의 무게와 무게당 가격이 주어졌을 때 배낭을 채울 수 있는 가장 값비싼 가격은 얼마인가? 루팡은 전동톱을 가지고 있으며 귀금속은 톱으로 자르면 잘려진 부분의 무게만큼 가치를 가진다. **제약조건 1 ≤ N ≤ 106인 정수 1 ≤ W ≤ 104인 정수 1 ≤ Mi, Pi ≤ 104인 정수 **입력형식 첫 번째 줄에 배낭의 무게 W와 귀금속의 종류 N이 주어진다. i + 1 (1 ≤ i ≤ N)번째 줄에는 i번째 금속의 무게 Mi와 무게당 가격 Pi가 주어진다. **출력형식..

2️⃣ GBC https://softeer.ai/practice/6270 💡 아이디어 구간은 100으로 고정이니 100개의 구간에서 각 구간별 스피드의 차이를 계산하여 풀이를 하였다. 처음에는 구간을 통째로 생각해서 아예 접근을 못했다 ㅜㅜ 1부터 100까지 각 칸마다 속도를 저장해서 빼주고, 그 차이가 가장 max인 것을 출력한다. 🖊️ 코드 import sys from collections import deque n, m = map(int, input().split()) part_speed = [0] * 101 dis_sum = 0 for i in range(n): # n만큼 거리와 속도를 받아온다 distance, speed = map(int, input().split()) # 현재위치부터 입력받은..

🥈 미로 탐색 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 192 MB 181911 82006 52295 43.640% 문제 N×M크기의 배열로 표현되는 미로가 있다. 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다. 입력 첫째 줄에..

3️⃣ 여행경로 https://school.programmers.co.kr/learn/courses/30/lessons/43164 💡 아이디어 ICN 공항에서 출발하여 공항 경로로 이동하는 것은 알겠는데, 문제는 가능한 경로가 2개 이상일 때 알파벳 순서가 앞서는 경로를 return하는 것을 어떻게 처리해줘야할지 전혀 감이안왔다. 예외를 고려하지 않고 BFS로 이렇게 생각했다. 그러나 각종 예외에 BFS로 어떻게 처리해야할지 난감해서 DFS로 방향을 틀었다 📝 풀이 생각을 바꿔보니 그냥 알파벳 순으로 미리 정렬하고 탐색하면 됐다. DFS로 푸는게 너무 어려웠다.. from collections import deque def solution(tickets): answer = [] for t in ticke..

3️⃣정수삼각형 https://school.programmers.co.kr/learn/courses/30/lessons/43105 💡 아이디어 가장 꼭대기에서 바닥까지 이동하고, 좌우 대각선 방향으로만 이동할 수 있다는 것을 이용하여 규칙을 찾았다. 각줄의 첫번째 수는 바로 직전의 첫번째 수를 이어받고, 마지막 수는 직전의 마지막 수를 이어받는다 그리고 나머지 수들은 대각선 좌우로 더 큰 값을 받는다 📝 풀이 def solution(triangle): for i in range(1, len(triangle)): # 둘째 줄부터 끝까지 for j in range(i+1): if j == 0: # 첫번째 수 triangle[i][j] += triangle[i-1][j] elif j == i: # 마지막 수 ..

🥈 곱셈 https://www.acmicpc.net/problem/1629 곱셈 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 0.5 초 (추가 시간 없음) 128 MB 108788 30296 22110 26.824% 문제 자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. 출력 첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다. 예제 입력 1 10 11 12 예제 출력 1 4 💡 아이디어 분할정복에 대한 개념을 잡아야 문제를 풀 수 있는 것 같다. 분할 정복 D..