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을 초기화해준다. (공기청정기는 움직이지..
https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net # BFS문제이다. # 100번 칸에 도착하기 위해 주사위를 굴려야하는 횟수의 최솟값을 구하는 문제 1. N개의 사다리의 (시작점, 끝점)과 M개의 뱀의 (시작점, 끝점)을 각각 dictionary에 넣어준다. 2. bfs()를 수행하는데, 처음에 1번칸에서 시작하므로 q에 1을 넣고 시작한다. 2-1. 현재 x번째 칸에서 k값을 더한 x+k가 다음칸..
https://www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net # '플로이드' 문제를 응용한 플로이드 2 문제이다. # a도시에서 b도시까지 가는 비용뿐만 아니라, a도시에서 b도시까지 가는 경로를 모두 출력해줘야 한다. # 경로를 찾는 코드를 구현하는데 꽤 많은 시간이 걸렸다... # 우선 path배열을 따로 선언해주고 a도시에서 b도시로 가는 a,b,c를 입력받을 때 dist[a][b]뿐만 아니라 path[a][b]도 [a, b]로 갱신해주었다. (a..
https://www.acmicpc.net/problem/2792 2792번: 보석 상자 보석 공장에서 보석 상자를 유치원에 기증했다. 각각의 보석은 M가지 서로 다른 색상 중 한 색상이다. 원장 선생님은 모든 보석을 N명의 학생들에게 나누어 주려고 한다. 이때, 보석을 받지 못하 www.acmicpc.net # 이분탐색 문제는 문제를 보고 '이분탐색으로 풀어야겠다' 라고 떠올리는 게 힘들다.. # 비슷한 문제로는 https://www.acmicpc.net/problem/16401 '과자 나눠주기' 문제가 있다. # jew에 보석의 개수를 입력받아 넣어주고 (1, max(jew))에서 binary_search를 실행시켜주면서 최적의 값을 구한다. # binary_search함수는 평소 이분탐색하듯이 짜면..
https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net # 처음에 그냥 숫자 3개씩 N줄을 m에 다 입력받고 풀었는데 메모리 초과가 났다. # 메모리제한이 4MB로 매우 작다. 따라서 dp배열도 N줄으로 만들면 안되고 3칸씩 2줄을 선언해서 계속 반복해주어야 한다. 입력되는 숫자들 역시 한번에 입력받으면 안되고 dp테이블을 갱신해줄때마다 한줄씩 입력받아 그때그때 처리를 해줘야 한다. # 최대점수, 최소점수를 구해야 하므로 min_dp, max_dp 배열 두개를 사용..
모르는 사이에 조금씩 조금씩..
