안녕

0. 문제 링크 https://www.acmicpc.net/problem/1938 1938번: 통나무 옮기기 첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4 ≤ N ≤ 50) 주어진다. 이어서 그 지형의 정보가 0, 1, B, E로 이루어진 문자열로 주어진다. 한 줄에 입력되는 문자열의 길이는 N이며 입력 문 www.acmicpc.net 1. 풀이 방법 BFS + 구현으로 문제를 풀었는데, 방문 처리가 가장 중요한 문제이다. 방문 처리와 더불어서 어떤 조건일 때 방문을 허락할지도 잘 체크해야 한다. 방문 처리는 비트 2개를 사용해서 해결하였다. 0은 미방문, 1은 가로가 방문, 2는 세로가 방문, 3은 가로세로 모두 방문 어떤 조건일 때 방문을 허락할지는 구현 문제이므로 이건 생략하겠다. 2..

0. 문제 링크 https://www.acmicpc.net/problem/2109 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 1. 풀이 방법 맨 처음 페이를 기준으로 정렬하고, 페이에 따른 기한 날짜에 넣는다. 만약 이미 그 기한 날짜에 다른 강의가 있다면 시간을 하루씩 당겨서 넣을 수 있는지 체크한다. 추가로 go to this day를 만들어서, 특정 기한 날짜의 강의는 this day의 날짜부터 강의를 할 수 있다고 정의한다. 또한 capacity를 만들어서, c..

0. 문제 링크 https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 1. 풀이 방법 다들 적군이 내려온다고 생각하는데, 나는 그냥 궁수가 올라가는 방식을 사용했다. 궁수가 적을 찾는 과정은 (우선순위에 따라)BFS로 해결하였고, 적을 찾으면 적의 위치를 반환하였다. 여러 궁수가 같은 적을 찾는 경우를 고려하여 적의 위치를 set으로 해결하였다. 궁수의 자리는 조합을 이용하여 BF하게 해결하였다. 2. 코드 import sys from itertools imp..

0. 문제 링크 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 1. 풀이 방법 문제는 위상정렬로 해결하였다. 다만 여기서는 중복이 발생할 수 있는데, 해결법은 두 가지로 나뉜다. set을 사용해서 후순위 노드를 하나만 집어넣고, degree도 1만 추가한다. list를 사용해서 후순위 노드를 (중복일지라도) 여러 개 집어넣고, degree도 여러 번 추가한다. 2.2번 해결법을 사용하면, 속도는 느려진다. 아무튼 최종적으로..

0. 문제 링크 https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 1. 풀이 방법 방향의 우선순위는 무조건 오른쪽 위, 오른쪽, 오른쪽 아래로 해야 한다. 그리고 왼쪽 상단부터 왼쪽 하단으로 차례로 돌면서 길을 찾는다. 나는 따로 방문 표시 복구를 하지 않았는데, 어차피 위에서 가지 못한 길이라면, 아래에서도 가지 못하는 길이기 때문에 복구하지 않았다. 따라서 dfs로 문제를 풀었다. 2. 코드 import sys input = sys.stdin.readline..

0. 문제 링크 https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 1. 풀이 방법 BFS 문제이고, 방문 표시를 잘해야 한다. 특정 키를 가지고 있음을 비트로 표현하는데, 방문 표시는 특정 키들을 가지고 이 칸에 방문한 적이 있느냐? 가 되겠다. 따라서 키는 총 6개이므로, 000 000 ~ 111 111의 경우의 수를 가질 수 있다. 따라서 총 64개의 경우의 수가 존재한다. 이제부터 모든 칸을 돌면서 특정 비트(..

0. 문제 링크 https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 1. 풀이 방법 육지를 찾으면 BFS를 통해 육지를 모두 같은 그룹 번호로 지정한다. BFS를 하면서 육지의 가장자리를 찾게 된다면 가장자리 BFS에 저장한다. 모든 육지를 찾으면 위에서 저장한 가장자리 BFS로 다른 육지를 탐색한다. 이때 나와 같은 그룹 번호를 찾는다면 패스하고, 다른 육지 번호일 때만 최단 거리를 업데이트한다. 만약 바다에서 BFS 하던 도중 기존의 최단 거리보다 ..

0. 문제 링크 https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 1. 풀이 방법 완전 탐색 비슷하게 풀었다. 참고로 BFS이다. 다만 최대 10억 개를 탐색해야 하는데, 이렇게 하면 무조건 시간초과가 난다. 최대 1,000,000의 길이이지만, 각 위치의 숫자는 0~9이다. 따라서 무조건 중복이 발생한다. 그러므로 중복을 잘 체크한다면 빠르게 풀 수 있다. BFS를 할 때는 실제로 자리를 바꿔줘서 해결하면 된다. *참고로 string끼리 대소비교 가능하다. 2. 코드 import sys from collection..

0. 문제 링크 https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 풀이 방법 while(특정 숫자가 들어오면 스택의 앞선 숫자와 비교한다.) 이때 들어오는 숫자가 더 크다면 스택을 팝한다. (k에 1씩 빼면서) 위 방식을 사용하면 앞자리가 큰 순서대로 스택에 쌓인다. 반복문을 탈출했는데, k가 0이 아니라면 이는 숫자가 대체적으로 내림차순이라는 의미이므로 스택에서 앞의 n - k개의 숫자를 출력한다. 2. 코드 import sys input = sys.stdin.readline def sol(): n, k = map(..

0. 문제 링크 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 1. 풀이 방법 에라토스테네스의 체로 maps에 소수인 부분은 True 설정한다. 기존의 방식(left, right를 양 끝에서 시작하여 점점 조여 오는 방식)이 아닌 left, right를 왼쪽부터 시작한다. total은 left와 right 사이에 있는 소수를 모두 더한 숫자이다. total을 기준으로 left 혹은 right을 옮긴다. 이때 left, right가 위치하는 index는 반드시 maps[index] == True여야 한다.(소수) total == n이라면 정답 += 1을 하고, l..