본문 바로가기

문제 해결/BOJ117

[백준] 등산 마니아 https://www.acmicpc.net/problem/20188 20188번: 등산 마니아 동네 뒷 산에는 등산로가 있다. 등산로는 N개의 작은 오두막들이 N −1개의 오솔길로 이어진 형태이다. 한 오솔길은 두 개의 오두막을 양 방향으로 연결한다. 한 오솔길의 길이는 1이다. 어떤 오 www.acmicpc.net import sys, math from collections import deque, defaultdict sys.setrecursionlimit(10 ** 8) #sys.stdin = open("input.txt", "r") input = sys.stdin.readline n = int(input()) dp = [0] * (n + 1) graph = defaultdict(list) for .. 2023. 4. 30.
[백준] 무기공학 https://www.acmicpc.net/status?from_problem=1&problem_id=18430 채점 현황 www.acmicpc.net 1. 문제 이해 N X M 크기의 직사각형에 강도를 의미하는 수가 적혀있습니다. 'ㄱ'모양으로 직사각형 내에서 선택할 수 있는데 노란 부분에 해당하는 곳은 강도의 영향을 2배로 받는다고 할 때 부메랑들의 강도의 합의 최대값을 구하는 문제입니다. 2. 문제 접근 첫번째 접근: 백트래킹 N, M 2023. 4. 29.
[백준] 프렉탈 평면 https://www.acmicpc.net/problem/1030 1030번: 프렉탈 평면 첫째 줄에 7개의 정수 s, N, K, R1, R2, C1, C2가 주어진다. www.acmicpc.net 1. 문제 이해 프랙탈 평면은 맨 처음 가장 큰 흰색 정사각형을 시작으로 규칙에 따라 흰색 정사각형과, 검은색 정사각형으로 쪼개지게 됩니다. 문제에서는 커진다고 표현했는데 점점 쪼개진다고 봐도 무방합니다. 한번 검정색인 정사각형은 쪼개져도 정사각형이 되고 흰색 정사각형은 시간에 지남에 따라 쪼개지면서 가운데 K X K 정사각형은 검은색으로 칠해지게 됩니다. 2. 문제 접근 첫번째 풀이: 분할정복 출력해야하는 직사각형의 크기가 최대 50 * 50 밖에 되지 않기 때문에 하나의 좌표가 흰색인지 검은색인지 판단해주.. 2023. 4. 27.
[백준] 파티 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 1. 문제 이해 각각의 도시에서 도시 -> X, X -> 도시 거리의 합이 가장 큰 값을 구하는 것이 문제입니다. 2. 문제 접근 첫번째 접근: 다익스트라 두 도시간의 최단거리를 구해야하므로 다익스트라를 생각했습니다. 각각의 도시에서 X까지의 최단 거리를 다익스트라로 구하고 X->도시까지의 거리를 다익스트라로 구한 다음 거리의 합의 최대값을 구해주었습니다. 두번째 접.. 2023. 4. 26.
[백준] Guess https://www.acmicpc.net/problem/1248 1248번: Guess Given a sequence of integers, a1, a2, …, an, we define its sign matrix S such that, for 1 ≤ i ≤ j ≤ n, Sij="+" if ai + … + aj > 0; Sij="−" if ai + … + aj < 0; and Sij="0" otherwise. For example, if (a1, a2, a3, a4)=( −1, 5, −4, 2), then www.acmicpc.net 1. 문제 이해 수열이 주어지고 i ~ j 범위내에 있는 숫자들을 더했을 때 양수이면 '+', 음수이면 '-', 0이면 '0'이 적혀있는 행렬이 주어집니다. 해당 행렬은 .. 2023. 4. 25.
[백준] 비즈 공예 https://www.acmicpc.net/problem/1301 1301번: 비즈 공예 첫째 줄에 다솜이가 가지고 있는 구슬의 종류 N이 주어진다. N은 3보다 크거나 같고, 5보다 작거나 같다. 둘째 줄부터 N개의 줄에 각각의 구슬이 총 몇 개 있는 지주어진다. 첫째 줄에는 1번 구슬, www.acmicpc.net import sys #sys.stdin = open("input.txt", "r") input = sys.stdin.readline n = int(input()) marble = [0] * 6 for i in range(n): marble[i] = int(input()) dp = [ [[[[[[-1 for _ in range(6)] for __ in range(6)] for ___ in r.. 2023. 4. 24.
[백준] 불우이웃돕기 https://www.acmicpc.net/problem/1414 1414번: 불우이웃돕기 첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선 www.acmicpc.net 1. 문제 이해 각각의 컴퓨터끼리 랜선으로 연결되어 있고 각각의 랜선은 길이가 있습니다. 다솜이가 가진 컴퓨터가 모두 연결된 상태를 유지하면서 필요 없는 랜선들은 기부하고자 할 때 기부할 수 있는 랜선 길이의 최댓값을 구하는 문제입니다. 2. 문제 접근 첫번째 접근: 최소 스패닝 트리 컴퓨터가 모두 연결되어 있어야하고 연결되어 있기 위해 필요한 최소한의 간선만을 유지하고 나머지 랜선은 기부하.. 2023. 4. 23.
[백준] 박스 채우기 https://www.acmicpc.net/problem/1493 1493번: 박스 채우기 세준이는 length × width × height 크기의 박스를 가지고 있다. 그리고 세준이는 이 박스를 큐브를 이용해서 채우려고 한다. 큐브는 정육면체 모양이며, 한 변의 길이는 2의 제곱꼴이다. (1×1×1, 2×2×2, www.acmicpc.net 1. 문제 이해 length * width * height 크기를 가진 박스가 주어지고 이 박스를 채우기 위해 2의 지수승을 한변으로 가지는 정육면체로 채우려고 할 때 필요한 큐브의 최소 개수를 구하는 문제입니다. 2. 문제 접근 첫번째 접근: 냅색 효율적인 냅색으로 박스를 채울 수 있는 방법에 대해 고민해보았지만 박스의 크기가 10 ^ 6 * 10 ^ 6 * 1.. 2023. 4. 22.
[백준] 내리막 길 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 1. 문제 이해 제일 왼쪽 위 칸에서부터 제일 오른쪽 아래 칸으로 이동할 때 계속해서 높이가 낮아지도록 이동할 수 있는 내리막길로만 이동하는 경로의 개수를 구하는 문제입니다. 2. 문제 접근 첫번째 접근: DFS 단순하게 왼쪽 위 칸에서부터 오른쪽 아래 칸으로 이동을 DFS로 풀이하면 시간초과가 날 것이라고 생각했습니다. 그래서내리막 경로에 해당하는 칸들에 방문처리를 하고 만약에 탐색 도중 방문 처리된.. 2023. 4. 21.

티스토리툴바