본문 바로가기

문제 해결/BOJ117

[백준] 싸지방에 간 준하 https://www.acmicpc.net/problem/12764 12764번: 싸지방에 간 준하 첫째 줄에 사람의 수를 나타내는 \(N\)이 주어진다. \((1 \le N \le 100,000)\) 둘째 줄부터 \(N\)개의 줄에 걸쳐서 각 사람의 컴퓨터 이용 시작 시각 \(P\)와 종료 시각 \(Q\)가 주어진다. \((0 \le P \lt Q \le 1,000 www.acmicpc.net 우선순위 큐와 dict 자료구조를 활용하여 풀이했습니다. 먼저, 컴퓨터의 최소 개수를 알아야합니다. time이라는 dict에 각 군인이 사용 시작에는 1을 사용 종료에는 -1을 넣어주고 시간을 오름차순으로 탐색하면서 누적합이 최대가 될때가 기다리지 않고 컴퓨터를 쓸 수 있는 최소의 개수가 됩니다. 최소 컴퓨터의 .. 2023. 3. 4.
[백준] 인싸들의 가위바위보 https://www.acmicpc.net/problem/16986 16986번: 인싸들의 가위바위보 두 사람이 같은 손동작을 내어 무승부가 발생할 경우 경기 진행 순서상 뒤인 사람이 이긴 것으로 간주함에 다시 한 번 유의한다. 구체적으로, 경기 진행 순서는 지우, 경희, 민호 순으로 고정되 www.acmicpc.net 완전 탐색, 백트래킹으로 풀 수 있는 문제입니다. 침착맨이 다르게 낼 수 있는 모든 손동작의 경우의 수 n!에 따른 경기 결과를 직접 시뮬레이션해보면 됩니다. 제 풀이는 침착맨이 낼 수 있는 모든 손동작의 경우를 만든 다음 시뮬레이션을 하기 때문에 시간이 조금 더 걸리지만 백트래킹으로 직접 라운드마다 낼 수 있는 손동작을 그때 그때 지정하는 방식으로 풀면 조금 더 짧은 시간안에 풀이가 가.. 2023. 3. 3.
[백준] 그리드 네트워크 https://www.acmicpc.net/problem/18769 18769번: 그리드 네트워크 재현이는 그리드 네트워크 컨설팅 회사를 운영하고 있다. 어떤 회사의 데이터 서버가 격자 형태의 그래프로 주어졌을 때, 최소의 비용을 들여서 전용 통신망을 설치하려고 한다. 이때, 전용 통 www.acmicpc.net 파이썬으로 인해 하루넘게 억까 당한 문제입니다. heapq를 사용하면 이 문제를 절대 통과가 불가능합니다. 따라서, 프림으로는 절대 풀 수 없고 우선순위 큐 대신 간선들을 정렬하여 크루스칼을 적용해주면 간신히 통과가 가능합니다. import sys from collections import defaultdict #sys.stdin = open("input.txt", "r") input = sys.. 2023. 3. 2.
[백준] Baaaaaaaaaduk2 (Easy) https://www.acmicpc.net/problem/16988 16988번: Baaaaaaaaaduk2 (Easy) 서기 2116년, 인간은 더 이상 AI의 상대가 되지 못하게 되었다. 근력, 순발력, 창의력, 사고력, 문제해결능력, 심지어 인간미조차 AI가 인간을 앞선다. AI가 온 지구를 관리하며 이미 인류는 지구의 www.acmicpc.net BFS를 활용하여 풀이하였습니다. 0으로 되어있는 칸들이 인간이 놓을 수 있는 위치들이므로 해당 위치들 중 2개를 뽑아서돌을 놓아보고 잡을 수 있는 최대 돌의 수를 얻는 방식으로 풀이하였습니다. 잡아먹을 수 있는 돌들의 집합인 경우를 체크하는 방법은 2번 돌들을 기준으로 BFS를 하다가 빈 공간을 만나면 잡아먹을 수 없는 그룹인 것을 이용하였습니다. im.. 2023. 3. 2.
[백준] 미로 탈출하기 https://www.acmicpc.net/problem/17090 17090번: 미로 탈출하기 크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다. 어떤 칸(r, c)에 적힌 문 www.acmicpc.net DFS로 해결할 수 있는 문제입니다. 현재 위치에서 시작으로 탈출이 가능한지 DFS로 탐색하게 됩니다. 만약 탈출이 가능하다면 DFS로 탐색하면서 만나는 위치들은 모두 탈출이 가능한 지점들입니다. 그러므로 해당 위치들에는 탈출이 가능하다고 체크해주고 만약에 탈출이 불가능하다면 만난 지점들은 모두 탈출이 불가능한 지점들입니다. 이렇게 탐색을 해주면서 탈출이 가능한 위치만 체크해주면 .. 2023. 3. 1.
[백준] 곡선 자르기 https://www.acmicpc.net/problem/14865 14865번: 곡선 자르기 컴퓨터 그래픽 캔버스는 컴퓨터 화면에서 그림을 그릴 수 있는 직사각형 영역을 말한다. 캔버스는 2차원 좌표 평면처럼 각 점의 위치를 좌표로 표시한다. 캔버스의 정중앙 점이 원점 (0,0)이고, www.acmicpc.net y좌표가 음수이고 가장 왼쪽에 있는 지점을 시작으로 x축을 통과할 때 아래에서 위로 통과하는 경우에는 봉우리가 시작되는 경우이고 위에서 아래로 통과하는 경우에는 봉우리가 끝나는 지점입니다. 모든 봉우리를 담아주고 봉우리가 시작하는 지점과 끝나는 지점을 각각의 status로 나누어서 TreeMap에 저장해둡니다. 그 다음 TreeMap을 탐색하면서 Stack을 통해 봉우리가 시작되는 시점을 담아.. 2023. 2. 27.
[백준] 연구소 3 https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 조합 + BFS를 사용하는 문제입니다. 조합을 통해 활성화시킬 바이러스들을 선택하고 선택한 바이러스들을 시작으로 BFS를 진행해주면 됩니다. 포인트는 선택되지 못해 비활성화되어 있는 바이러스들을 만나는 경우인데 이 경우에는 큐에는 넣어주지만 모든 빈칸을 바이러스로 만들기 위해 필요한 시간으로 체크되면 안됩니다. import sys from itertools import combinations from co.. 2023. 2. 26.
[백준] 일감호에 다리 놓기 https://www.acmicpc.net/problem/17490 17490번: 일감호에 다리 놓기 2번, 4번, 5번 강의동과 와우도를 연결하면 가지고 있는 돌 내에서 징검다리를 완성할 수 있다. 이 때, 어떤 한 강의동에서 다른 모든 강의동으로 가는 길이 존재한다. www.acmicpc.net 정답률이 매우 낮아서 걱정했지만 생각보다 그리 어렵지않게 풀 수 있었던 문제입니다. 원형으로 이어져있는 그래프에서 각각의 연결 그래프를 이루고 있는 강의동들 중 가장 작은 돌다리가 필요로하는 강의동에만 연결해주면 됩니다. 이렇게 했을 때에 K개를 넘어가면 불가능하므로 NO를 출력해주면 됩니다. 조심해야하는 점은 돌다리를 놓지 않고도 연결되어 있는 경우가 있습니다. 정답률이 낮은 이유는 아마도 C++이나 JAV.. 2023. 2. 25.
[백준] 문자열 폭발 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 스택을 활용한 문제입니다. 문자들을 스택에 쌓아주면서 마지막 문자열이 매칭하고자하는 문자열과 비교해서 같으면 stack에서 pop하여 버리면 풀 수 있습니다. import sys # sys.stdin = open("input.txt", "r") input = sys.stdin.readline inputs = list(input().rstrip()) matching = input()... 2023. 2. 24.

티스토리툴바