김머성 블로그

[BAE/<JOON> 문제풀이] 20047. 동전 옮기기

핵심:: 구현(?) 풀이 DP 태그 붙어 있어서 점화식 찾으려다 못찾고 결국 재귀로 풀이했다. ( Top Down 방식으로 풀이 했기 때문에 DP가 맞긴 하다 ) 풀이:: 이동 가능한 2개의 동전 배열과 초기 동전 배열에서 그 동전 2개를 뺀 배열 2개를 만든다 ex) 6 oooxxx oxoxox 1 2 => 이 경우, 각각의 배열은 다음과 같이 분리 된다. arr1 = oxxx arr2 = oo 이 분리된 배열들을 앞쪽부터 적절히 순서를 섞어 주어진 2번째 배열(예제 oxoxox)을 만들 수 있는지 여부를 검사하면 된다. 이 부분은 그냥 구현 쪽이고 두 배열의 몇번째 인덱스를 사용했을 때 결과가 정해지는지 여부만 DP 배열에 따로 저장했다. 의견:: DP 정해가 뭔지 궁금하다. 이게 왜 DP지 코드::..

[BAE/<JOON> 문제풀이] 14621. 나만 안되는 연애

https://www.acmicpc.net/problem/14621 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 핵심:: MST 기본 문제 풀이:: 처음보고 프림 알고리즘 + 이분 그래프 개념으로 풀어야하나 싶었다. 하지만 간단하게 생각해보면 그냥 양 끝단의 성별이 같은 간선 자체를 제외하면 크루스칼 알고리즘으로 해결 할 수 있다. 의견:: 프림 알고리즘 한번도 구현 안해봐서 풀기 싫었는데 프림 아니었음 프림으로도 구현 자체는 될 거 같다. 코드:: 더보기 #incl..

[BAE/<JOON> 문제풀이] 1513. 경로 찾기

https://www.acmicpc.net/problem/1513 1513번: 경로 찾기 첫째 줄에 0개 방문했을 때, 1개 방문했을 때, ..., C개 방문했을 때 총 경로의 개수를 한 줄에 공백을 사이에 두고 출력한다. 경로의 개수는 1,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 1513:: 경로 찾기 핵심:: 기본 DP 문제 고려해야할 요소들이 많기는 하지만 기본 DP 문제 틀에서 벗어나지는 않음 풀이:: DP[x 위치][y 위치][방문한 오락실 중 최대 번호][방문한 오락실 갯수] = 위 조건을 만족하는 경로 갯수 점화식은 다음과 같음 현재 칸이 오락실일 경우:: 현재 칸으로 올 수 있는 윗칸과 아랫칸에서 방문한 오락실 번호가 현재 오락실 번호보다 작은 모든 오락실 경로..

[BAE/<JOON> 문제풀이] 2146. 다리 만들기

https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 2146:: 다리 만들기 핵심:: BFS 풀이:: 1. 섬을 찾고 번호 부여 -> 찾은 섬 부분을 모두 큐에 집어넣고 2번 탐색 시작 2. 섬 경계를 확장하며 서로 다른 번호를 가진 섬 경계가 맞닿는 경계 찾기 3. 최소값 초기화 풀이 로직은 간단한데 코드가 좀 길다. 의견:: 진짜 쉬워뵈는데 까다로움 코드:: 더보기 #include #include #include using namespace std;..

[BAE/<JOON> 문제풀이] 13302. 리조트

https://www.acmicpc.net/problem/13302 13302번: 리조트 수영이는 여름방학을 맞이하여 많은 놀이 시설이 있는 KOI 리조트에 놀러가려고 한다. 리조트의 하루 이용권의 가격은 만원이다. 하지만 리조트의 규모는 상상을 초월하여 모든 시설을 충분히 www.acmicpc.net 핵심:: DP 점화식 풀이:: DP[이용시간][쿠폰개수] = 최소가격 이용권 종류가 총 3가지이므로 각각의 이용권마다 배열로 정보를 만들면 편리하다. 쿠폰을 사용하는 행동도 이용권으로 보고 쿠폰 -3개를 얻어 하루를 이용할 수 있는 가격 0원의 이용권으로 등록했다. 바텀-업 방식으로 풀이 했으므로 최대 쿠폰 개수를 알아야 DP 배열을 만들 수 있는데, 그냥 대충 100개 짜리 배열로 만들고 90개 까지만 ..

[BAE/<JOON> 문제풀이] 14442. 벽 부수고 이동하기 2

https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 핵심:: 기본 BFS 문제 풀이:: 이 문제는 벽을 뚫고 이동할 수 있는 횟수가 1 이상이으므로 각 지점에서 벽을 뚫을 수 있는 횟수 별로 최단 거리를 따로 저장을 해줘야 한다. 의견:: 코드:: 더보기 #include #include #include #include #include using namespace std; struct node { int x, y,..