본문 바로가기

코딩 테스트/백준

 (121)
[Python] 백준 16236 아기 상어 https://www.acmicpc.net/problem/16236 문제 분석N x N 크기M마리 물고기와 아기상어 1마리한 칸에 최대 1마리의 물고기아기 상어와 물고기는 모두 크기를 가지고 있고, 크기는 자연수가장 처음의 아기상어 크기는 2아기상어는 1초에 상하좌우로 인접한 한 칸 씩 이동조건아기상어는 자신의 크기보다 작거나 같은 물고기가 있는 칸만 지나갈 수 있다.자신보다 작은 물고기만 먹을 수 있다.더 이상 먹을 수 있는 물고기가 공간에 없으면 엄마 상어에게 도움 요청먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.먹을 수 있는 물고기가 1마리보다 많다면 거리가 가장 가까운 물고기를 먹으러 간다.거리 : 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때 지나야하는 칸의 개수의 최..
[Python] 백준 2583 영역 구하기 https://www.acmicpc.net/problem/2583 문제 분석눈금 간격이 M x N 크기의 모눈종이눈금에 맞춰 K개의 직사각형을 그릴 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어 지는가그리고 각 영역의 넓이는 얼마인가 풀이넓이 우선 탐색 (bfs) 코드 설계직사각형 영역 찾기직사각형 영역 : 1직사각형 x : 0영역 찾기 0이고, 아직 방문하지 않았으면 덱에 넣기같은 영역의 범위 구하기모눈종이의 범위를 벗어나지 않고아직 방문하지 않았으며g 좌표의 값이 0이면 append → 가능한 영역 : area += 1 정답 코드import sysfrom collections import dequeinput = sys.stdin.readlineM, N, K = ma..
[Python] 백준 1238 파티 https://www.acmicpc.net/problem/1238 문제 분석N개의 숫자로 구분된 마을에 한 명의 학생이 살고 있다.N명의 학생이 x (1 이 마을 사이에는 총 M개의 단방향 도로들이 있고, i번째 길을 지나는데 Ti (1 각 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. - 최단거리오고가는 길이 다를 수 있다.N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구인가 풀이N명의 학생M 개의 이동할 수 있는 도로 정보 (단방향, 가중치)X : 모이는 곳1 ~ N 까지 반복distance[ i ] = i ~ X 의 최단거리 + X ~ i 의 최단거리이 중 가장 큰 값을 출력 코드 설계X에서 1~N까지의 최단거리는 다익스트라로 한번에 구하기1 ~ N까..
[Python] 백준 9095 1,2,3 더하기 https://www.acmicpc.net/problem/9095 문제 분석n이 주어졌을 때, n을 1,2,3의 합으로 나타내는 방법의 수를 구하라 풀이순서x, 중복o → 중복 조합 (product)dp뭘 저장해야 할까?초기조건2 = 1+12 = 2 3 = 1+1+13 = 1+23 = 2+13 = 3새로운 숫자에 대해 다음을 굳이 또 계산할 필요가 없다.  정답 코드1. 중복 조합import sysinput = sys.stdin.readlinefrom itertools import producttc = int(input())for _ in range(tc) : ans = 1 n = int(input()) nums = [1,2,3] for i in range(1, n) : # 1을 n..
[Python] 백준 2217 로프 https://www.acmicpc.net/problem/2217 문제 분석N개의 로프각 로프는 들 수 있는 물체의 중량이 서로 다를 수 있다.로프를 병렬로 연결하여 중량이 w인 물체를 들어올릴 때, 각 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.각 로프의 정보가 주어졌을 때, 로프들을 사용하여 들어올릴 수 있는 물체의 최대 중량은?모든 로프를 다 사용하지 않아도 된다. 풀이중량은 정확하게 w/k로 나눔으로 k개의 로프에 대해 최대로 들 수 있는 무게는 k중 가장 적게 들 수 있는 중량 x k 이다.로프의 길이에 대해 내림차순으로 정렬한 뒤각 로프가 추가될 때마다 들 수 있는 최대 중량을 저장한다.1 dp ? 코드 설계작은 로프에 대해 로프가 들 수 있는 무게가 달라지므로 내림차순으로 정렬한..
[Python] 백준 2212 센서 https://www.acmicpc.net/problem/2212 문제 분석도로 위 N개의 센서를 설치센서들이 수집한 자료들을 모으고 분석할 몇 개의 집중국을 세우려고 하는데 K의 집중국을 세울 수 있다.각 집중국은 센서의 수신 가능 영역을 조절할 수 있다.집중국의 수신 가능 영역 : 고속도로 상에서 연결된 구간으로 나타나게 된다.N개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 하며집중국의 수신 가능 영역의 길이의 합을 최소화직선의 고속도로센서들은 직선 위의 한 기점인 원점으로부터 정수 거리의 위치에 놓여 있다.각 센서의 좌표는 정수 하나로 표현각 좌표 사이에 빈 칸 하나? 풀이어떻게 집중국의 수신 가능 영역의 길이의 합을 최소화할 수 있을까?가까운 센서들끼리 묶어서 집중국이 관리를 해야 수신 가..
[Python] 백준 1697 숨바꼭질 문제 분석시작 위치 : N, 도착 위치 : KX에서걷는 다면 : X-1, X+1순간이동 : X*2 풀이각 이동하는 칸에 대하여 최단 거리 구하기각 칸에 대한 이동 시간 기록dpdfs ? 코드 설계  정답 코드1차 - 메모리초과import sysinput = sys.stdin.readlinefrom collections import dequen, k = map(int, input().split())def dfs() : d = deque() d.append((n, 0)) while d : x, cnt = d.popleft() if x == k: print(cnt) break d.append((x + 1, cnt + ..
[Python] 백준 13975 파일 합치기 3 문제 분석소설을 챕터마다 쓰는데 각 챕터는 다른 파일에 저장한다.소설의 모든 챕터를 쓰고 나서 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다.여러 챕터를 합치는 과정에서 두 개의 파일을 합쳐서 하나의 임시 파일을 만들고,이 임시 파일이나 원래의 파일을 계속 두 개씩 합쳐서 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다.두 개의 파일을 합칠 때 필요한 비용 = 두 파일 크기의 합최종적인 한 개의 파일을 완성하는 데 필요한 비용의 총 합 정답 코드실패import sys, heapqinput = sys.stdin.readlinetestcase = int(input())for tc in range(testcase) : chap = int(input()) ..

티스토리툴바