https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net # 꽤 까다로운 BFS 문제이다. # 이 문제를 푸는데 있어서 주의할 점은 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없으므로 물을 먼저 흘려보낸 뒤 고슴도치를 이동시켜야 한다는 것이다. # dist_beaver는 고슴도치가 이동하는데 걸리는 시간, dist_water는 물이 차는데 걸리는 시간 두 가지 배열로 상태를 나타내고 비교했다. # bfs_water함수를 통해 먼저 물을 흘려보낸 뒤, ..
https://www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net # BFS 문제이다. # 1번 후보부터 N번 후보까지 각각 bfs함수를 실행해 dist값을 갱신해준다. (dist값 = 현재 후보와의 거리 = 문제에서 요구하는 '점수') # dist값의 최대가 현재 후보의 점수이다. 따라서 점수가 가장 작은 사람이 회장후보이므로 chairman 배열에 회장후보들을 넣어준다. 마지막에 점수와, 후보 수, 후보들을 출력해주면 끝 import sys from coll..
https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net # 2019년 하반기 삼성SW 역량테스트 문제이다. # 문제를 이해하는데 오래 걸렸다. 그림만 보면 금방 이해가 갔을텐데, 글로 길게 써놓으니 헷갈렸다.. # 5개의 선거구로 나누고 각각의 선거구의 인구 합을 구한 뒤, 인구가 가장 많은 선거구와 가장 작은 선거구의 인구 차이를 구하는 문제이다. # (x, y, d1, d2) = (1, 1, 1, 1)부터 (N-2, N-2, N-2, N-2)까지 완전탐..
https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net # 2017 하반기 삼성SW 역량테스트 문제이다. # 단순 구현, 시뮬레이션 문제라 어렵지 않았다. # 톱니바퀴도 4개로 고정이고, 톱니개수도 8개여서 그냥 브루트포스형식으로 풀면된다. import sys from collections import deque input = sys.stdin.readline gear = {} for i in range(4): gear[i+1] = deque(in..
https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net # 2020년도 상반기 삼성SW 역량 테스트문제이다. # 삼성답게 구현이 꽤 까다로웠지만, 그래도 문제에서 요구하는대로 짜면 풀리는 문제이다. import sys from collections import deque input = sys.stdin.readline customer = {} q = deque() N, M, F = map(int,input().s..
https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net # 2017년도 삼성SW역량 테스트 상반기 문제이다. # 골드치곤 그냥 하라는 대로 짰더니 바로 맞춰서 쉬운 문제였다. # 방향 4가지 경우를 나누어주고 2-a, 2-b, 2-c, 2-d경우를 다 나눠서 코드를 짰다. # 한 가지 고려해야할 요소는 2-d에서 뒤쪽 방향이 '벽인 경우'에만 작동을 멈춰야 한다. 뒤쪽 방향이 청소는 되어있지만, 벽이 아닌 경우 후진은 할 수 있기 때문이다. 따라서 ..
https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net # 다익스트라 문제이다. # 기본적인 다익스트라 문제에서 특정한 경로 v1과 v2 정점을 무조건 지나가야 한다는 조건이 붙었다. # 1번 정점부터 N번 정점까지 가는데 있어서 v1, v2정점을 지나는 경우는 2가지 존재한다. A. 1번 -> v1 -> v2 -> N번 B. 1번 -> v2 -> v1 -> N번 # 다익스트라를 3번 돌려서 (1번 정점부터..
https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net # 2019년 상반기 삼성 SW 역량테스트 문제이다. # 역시 삼성답게 엄청난 끈기와 인내력을 필요로 하는 빡구현+시뮬레이션 문제였다.. # 우선 T초동안 시뮬레이션을 돌려야하니 while T를 해준다 시뮬레이션을 돌리는 매 초마다 각각 새로 먼지위치, 먼지 양을 구해야 하므로 매 초마다 먼지 위치를 저장하는 dust와 공기청정기 위치를 저장하는 clean을 초기화해준다. (공기청정기는 움직이지..
모르는 사이에 조금씩 조금씩..
