김머성 블로그

[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 기본 문제 풀이:: 처음보고 프림 알고리즘 + 이분 그래프 개념으로 풀어야하나 싶었다. 하지만 간단하게 생각해보면 그냥 양 끝단의 성별이 같은 간선 자체를 제외하면 크루스칼 알고리즘으로 해결 할 수 있다. 의견:: 프림 알고리즘 한번도 구현 안해봐서 풀기 싫었는데 프림 아니었음 프림으로도 구현 자체는 될 거 같다. 시간 복잡도는 만족 시킬지..

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

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

[BAE/<JOON> 문제풀이] 1175. 배달

https://www.acmicpc.net/problem/1175 1175번: 배달 어제 선물을 모두 포장한 민식이는 이제 선물을 배달하려고 한다. 민식이가 선물을 배달할 곳은 이 문제를 읽는 사람들이 앉아 있는 교실이다. 교실은 직사각형모양이고, 모두 같은 크기의 정사 www.acmicpc.net 핵심:: 진입 방향에 따라서 거리 따로 계산 풀이:: 같은 방향으로 2번 이상 나아갈 수 없으므로 어떤 지점의 최솟값을 기록할 때 들어가는 방향도 고려해야한다. 다음과 같은 경우를 생각해보면 쉽게 이해할 수 있다. 빨간 타일에서 1번 방향으로 움직인 거리를 기록할 때 3번 방향에서 들어왔을 때의 최솟값은 고려하면 안된다. 하지만 만약 타일 당 하나의 최소거리를 기록한다면 3번 타일까지의 거리가 가장 가까웠을 ..

[BAE/<JOON> 문제풀이] 2643. 색종이 올려놓기

https://www.acmicpc.net/problem/2643 2643번: 색종이 올려 놓기 첫 번째 줄에는 색종이의 장수가 주어진다. 다음 줄부터 각 줄에 색종이의 두 변의 길이가 주어진다. 두 변의 길이는 한 칸 띄어 주어진다. 색종이의 최대 장수는 100이고, 각 변의 길이는 1000보다 www.acmicpc.net 핵심:: 색종이 정렬 풀이:: 색종이를 큰 변의 크기 위주로 정렬하고 각 단계에서 윗쪽의 색종이들 중 몇개를 올려놓을 수 있는지 검사한다. 이 때 같은 색종이를 여러번 세게 되므로 (a -> b -> c 순서로 먹힌다면 a -> b 에서 a 한번 (a, b) -> c에서 한번) 이 부분을 중복계산하지 않도록 코딩하면 된다. DP 배열에 해당 번호의 색종이 위에 올려놓을 수 있는 개수..

[BAE/<JOON> 문제풀이] 1019. 책 페이지

https://www.acmicpc.net/problem/1019 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 핵심:: 당연히 자리수 별로 나눠서 숫자 갯수를 구하는 규칙을 찾는 것이다. 입력의 크기가 10^9 이므로 자릿수 별로 나눠서 숫자를 세는 방법은 시간 제한을 만족시킬 수 없다. 풀이:: 각 자릿수마다 0 ~ 9의 숫자들이 몇개씩 나오는지 체크하여 더하는 방식으로 구현하였다. 규칙은 다음과 같다. N 자리 수의 K번째 자릿수에 숫자 m의 등장 횟수 구하기 ( 1의 자리 K = 0 ) 1. K자릿수를 기준으로 0 ~ (K - 1) (이하 back)구간과 (K + 1..

[BAE/<JOON> 문제풀이] 1577. 도로의 개수

https://www.acmicpc.net/problem/1577 1577번: 도로의 개수 첫째 줄에 도로의 가로 크기 N과 세로 크기 M이 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 둘째 줄에는 공사중인 도로의 개수 K가 주어진다. K는 0보다 크거나 같고, 100보다 작거나 같은 www.acmicpc.net 핵심:: 도로를 잘 구분 짓는게 중요함 풀이:: 이 문제를 틀리는 이유는 공사중인 도로를 식별하는 방법을 잘못 정하는 오류를 범했을 확률이 높다. 직접 다 하나씩 해봐서 틀려봤으므로 하나씩 나열해보겠다. 1. 배열에 공사도로 시작점과 끝점을 표시하고 공사중인 지점일 경우 경우의 수 0으로 처리 -> 가장 간단한 오류다. 한 점마다 4개의 도로가 있는데 공사중이지 않은 나머지 3개의 ..