coding- w00se

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 한 지역의 높이 정보가 NXN 배열로 주어지고 비로 인해 물에 잠기지 않은 서로 연결된 영역을 안전 영역이라 할 때, 장마철에 안전 영역의 최대 개수를 구하는 것이 이 문제의 목표입니다. 이 문제에서는 내리는 비의 양은 입력으로 주어지지 않습니다. 하지만, 지역의 높이의 최소 높이와 최대 높이를 알 수 있으므로 비의 양을 적절히 조정하여 테스트를 진행할 수 있습니다. 해당 문제는 그래프 탐색 문제로, 저..

https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 출발지(상근이의 집)에서 출발해서 목적지(페스티벌 장소)까지 갈 수 있는지 판단하는 것이 이 문제의 목표입니다. 단, 현재 장소에서 거리가 맨해튼 거리로 1000 이하인 다음 장소(편의점 또는 목적지)로만 이동 가능하다는 조건이 있습니다. 이 문제는 그래프 탐색 문제입니다. 탐색은 너비 우선(BFS)으로 진행해도 되고, 깊이 우선(DFS)으로 탐색해도 되는 거 같습니다. 저는 깊이 우선 탐색..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 그래프에서 최소 비용을 구하는 문제로 다익스트라 알고리즘이 사용되는 대표 문제입니다. * 다익스트라 알고리즘: 한 노드에서 다른 모든 노드로의 최소 비용(=최단 거리)을 계산할 때 사용되는 방법 접근 방식 1. 입력된 모든 노드와 간선 정보를 저장 2. 다익스트라 알고리즘을 이용해서 출발 도시에서 모든 도시로의 최소 비용을 계산 3. 2단계에서 계산된 출발 도시에..

https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 이 문제는 구현 문제입니다. 입력으로 NXN 배열에 저장된 값이 주어지고, 주어진 문제 조건대로 명령을 수행한 후 마지막에 NXN 배열에 저장된 값의 합을 구하는 것이 이 문제의 목표입니다. 접근 방식 1. 입력 값을 입력받기 2. 초기 구름의 위치 정보를 1차원 배열인 cloud_list와 2차원 배열인 cloud_mat에 저장 cloud_list: 구름의 위치 정보(행, 열 값) 저장한..

https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 이 문제는 입력으로 저장해야 하는 N개의 숫자와 찾아야 하는 M개의 숫자가 주어지고, 각각의 찾아야 하는 수가 저장한 수 목록에 존재하는지 확인하는 것이 목표입니다. 문제를 해는 방법은 다양하게 존재하지만 저는 이분 탐색으로 문제를 해결했습니다. 전체 코드 제출 언어: Python3 시간: 600ms import sys def findNum(targ..

https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 그래프 문제입니다. 입력으로 부모-자식 관계가 주어지고 주어진 두 사람의 촌수를 구하는 것이 이 문제의 목표입니다. 저는 깊이 우선 탐색(dfs)으로 이 문제를 해결했습니다. 접근 방식 1. 입력으로 주어진 가계도를 2차원 배열에 저장합니다. 2. 촌수를 계산해야 하는 사람을 각각 p1, p2라고 할 때, p1을 시작으로 탐색을 진행합니다. 3. 현재 탐색하는 사람과 관계가 있..

https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 전체 코드 제출 언어: PyPy3 시간: 1400ms import sys def check_is_success(): global N, H, mat is_success = True for i in range(1, N+1): d = 0 idx_left, idx_right = i-1, i for j in range(H): if mat[j][idx_left]: d -= 1 idx_left -= 1 id..

https://www.acmicpc.net/problem/17825 17825번: 주사위 윷놀이 첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다. www.acmicpc.net 이 문제는 백트래킹, 구현 문제입니다. 주사위를 굴려서 나올 10개의 숫자를 미리 알려주고, 말을 이동시켜 얻을 수 있는 최대 점수를 구하는 것이 이 문제의 목표입니다. 이 문제는 이름에도 윷놀이가 있듯이 윷놀이처럼 지름길이 있습니다. 지름길은 10, 20, 30 칸에서 출발을 해야 갈 수 있으며 이동 중간에 해당 칸들을 지나는 경우는 지름길로 갈 수 없습니다. 말은 해당 회차에서 주사위를 굴려 나온 수 만큼 진행방향으로 이동시킵니다. 다만, 이동시킬 칸에 이미 말이 존재하면 해당 말은 이동시킬 수 없습니다.(도착 칸은 제..

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 이 문제는 너비 우선 탐색(bfs) 문제입니다. 배열 안의 각 칸은 나라를 의미하며, 조건에 맞을 시 주변 국가와 국경을 개방하여 인구를 이동시킵니다. 인구 이동은 매일 진행되며, 이 문제의 목표는 인구 이동이 며칠 동안 발생하는지 구하는 것이다. 접근 방식 1. 날마다 연합국 정보를 초기화한다.(어떠한 연합국에든 속하는지/속하지 않는지 판단하는 정보를 저장) 2. 각 국가를 순회하..

https://www.acmicpc.net/problem/17610 17610번: 양팔저울 무게가 서로 다른 k개의 추와 빈 그릇이 있다. 모든 추의 무게는 정수이고, 그릇의 무게는 0으로 간주한다. 양팔저울을 한 번만 이용하여 원하는 무게의 물을 그릇에 담고자 한다. 주어진 모든 추 www.acmicpc.net 전체 코드 제출 언어: PyPy3 시간: 260ms import sys if __name__ == "__main__": k = int(sys.stdin.readline().strip()) weights = list(map(int, sys.stdin.readline().strip().split())) weights.sort() max_num = sum(weights) candidates = [ w..