바위 뚫는중

🥈 등수 매기기 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..

2️⃣ 프로세스 문제 운영체제의 역할 중 하나는 컴퓨터 시스템의 자원을 효율적으로 관리하는 것입니다. 이 문제에서는 운영체제가 다음 규칙에 따라 프로세스를 관리할 경우 특정 프로세스가 몇 번째로 실행되는지 알아내면 됩니다. 1. 실행 대기 큐(Queue)에서 대기중인 프로세스 하나를 꺼냅니다. 2. 큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면 방금 꺼낸 프로세스를 다시 큐에 넣습니다. 3. 만약 그런 프로세스가 없다면 방금 꺼낸 프로세스를 실행합니다. 3.1 한 번 실행한 프로세스는 다시 큐에 넣지 않고 그대로 종료됩니다. 예를 들어 프로세스 4개 [A, B, C, D]가 순서대로 실행 대기 큐에 들어있고, 우선순위가 [2, 1, 3, 2]라면 [C, D, A, B] 순으로 실행하게 ..