구빙그르르르

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N 첫자리부터 더해가면 증가만 한다. -> 정렬의 효과 2. 부분합을 어떻게 구할것인지 -> 완전탐색을 통해 구할 수 있지만 N이 100000까지 가능하므로 시간초과 발생 -> 따라서 dp를 ..

https://www.acmicpc.net/problem/27172 27172번: 수 나누기 게임 《보드게임컵》을 준비하다 지친 은하는 보드게임컵 참가자들을 경기장에 몰아넣고 결투를 시키는 게임 《수 나누기 게임》을 만들었습니다. 《수 나누기 게임》의 규칙은 다음과 같습니다. www.acmicpc.net 문제 한줄 이해 - 각자 숫자가 적힌 카드를 가지고 있을 때 내 카드로 상대방 카드를 나눴을 때 나머지가 0이면 +1점을 얻지만 반대로 나누어 지면 -1점을 얻고 다른 경우에는 무승부로 0점을 얻을 때 각 점수 구하기 생각난 풀이 문제를 읽고 생각난 필요한 조건들 1. 먼저 간단히 모든 경우의 수를 파악해주면 되는거 아니야? 라는 생각에 이중 포문을 사용했다. import sys n = int(sys.s..

https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 문제 한줄 이해 - 용액의 특성을 나타내는 정수가 주어졌을 때 용액들을 섞어 최대한 0의 가까운 경우를 구하기 생각난 풀이 문제를 읽고 생각난 필요한 조건들 1. 먼저 문제에서 입력이 정렬된 상태에서 들어온다, n의 값이 크다 -> 투포인터, 이분탐색을 예상해볼 수 있다. 2. 값들 중 2개를 골라 모든 경우의 수를 파악해 제일 작은 경우를 구하면 되지만 시간 복잡도에서 문제가 생긴다 -> ..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제 한줄 이해 - N*N격자에 아기상어와 물고기가 있을 때 문제에서 주어진 조건에 맞춰 엄마상어를 부르기 전까지의 시간을 구하기 생각난 풀이 문제를 읽고 생각난 필요한 조건들 문제가 길기도 했고 필요한 조건들이 많다고 생각이 들었다. -> 다행히 문제풀이에 필요한 조건 뽑기 연습을 하고 있어서 다행이다!! 1. 아기상어를 기준으로 각 물고기들까지의 거리를 구하기 -> 아기상어의 위치를 기..

https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 문제 한줄 이해 - 노드들의 최단 경로와 거리를 출력하기 생각난 풀이 1번째 방법: 문제를 읽고 생각난 필요한 조건들 1. 저번에 풀어본 https://9-bin.tistory.com/37 에서 경로까지 출력해야하는 경우다. ->다익스트라, 경로저장 -> 경로를 어떻게 저장을 해야할지 고민을 해봤지만 쉽사리 떠오르지 않았다. 이때 검색을 해보니 역추적이라는 키워드를..

https://www.acmicpc.net/status?user_id=imagen33&problem_id=2638&from_mine=1 채점 현황 www.acmicpc.net 문제 한줄 이해 - 격자에 치즈와 공기로 채워져 있을 때 치즈가 2변 이상이 공기와 맞닿아(단 치즈로 둘러쌓인 공기는 영향을 주지 않는다) 있으면 한시간마다 녹아서 없어져 버린다고 한다. 이때 총 몇시간이 지나야 다 녹는지 구하기! 생각난 풀이 1번째 방법: 문제를 읽고 생각난 필요한 조건들 1. 우선 각 치즈에 공기에 맞닿는 부분이 몇변인지 세기 -> 먼저 BFS로 0,0부터 탐색을 시작한다 why? 문제에서 가장자리는 무조건 공기라고 주어졌다. 이때 0,0부터 탐색을 진행해 공기일때만 탐색 대상으로 삼으면 치즈로 둘러쌓인 내부는..

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 문제 한줄 이해 - N개의 숫자로 구분된 마을에 각각 한 명의 학생이 있을 때 X번 마을에서 학생들이 파티를 하기로 했다. 이때 마을에서 마을로 연결하는 단방향 거리가 있을 때 가장 많은 거리를 이동해야하는 학생의 거리값 구하기. 생각난 풀이 1번째 방법: 문제를 읽고 생각난 필요한 조건들 1. 각 마을들을 가중치에 따라 연결하고 있다. -> 다익스트라 알고리즘이나 ..

https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 문제 한줄 이해 - 그래프에 공기청정기와 미세먼지들이 있을때 1초동안 하는 일련의 과정이 진행되고 총 미세먼지 양을 구하기 생각난 풀이 1번째 방법: 문제를 읽고 생각난 필요한 조건들 1. 1초동안 어떤 과정들이 이루어지는지 파악 1-2. 각 미세먼지들이 상하좌우로 퍼진다. -> 먼지들이 있는곳을 큐에 담아 상하좌우 탐색하기 1-3. 그런다음 공기청정기에 의해 미세먼지들이 이동한다. -> 그래프..

https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 문제 한줄 이해 - 주어진 노드들 사이의 최소 거리를 구하고 제시된 거리보다 낮은 곳을 방문해 최대한 많은 양의 아이템을 구하는 경우를 출력하기 생각난 풀이 1번째 방법: 문제를 읽고 생각난 필요한 조건들 1. 각 노드들 사이의 최소거리 구하기 why? 문제에서 예은이는 정해진 범위 m만큼만 이동 할 수 있다고 한다. 2. 각 노들드의 아이템 수를 담을 리스트를 따로 만들어 놓기 3. 어떤 노드에 예은..

https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 문제 한줄 이해 - 나와 동생의 위치가 주어지고 1초 뒤에 +1, -1 ,*2의 위치로 이동 할 수 있을 때 동생의 위치로 가는 빠른 시간과 빠른 시간의 경우의 수 구하기 생각난 풀이 1번째 방법: 현재 위치에서 1초뒤에 3가지 경우로 뻗어 나간다. 또한 뻗어 나간 그 위치에서도 각각 3가지 경우로 뻗어 나가는 상황을 생각하면 그래프 탐색이 떠올랐다!! 그래서..