문제 https://www.acmicpc.net/problem/18232 18232번: 텔레포트 정거장 첫 번째 줄에 정수 N, M이 공백으로 구분되어 주어진다. (2 ≤ N ≤ 300,000, 0 ≤ M ≤ min(N×(N-1)/2, 300,000)) 두 번째 줄에 정수 S, E가 공백으로 구분되어 주어진다. (1 ≤ S, E ≤ N, S ≠ E) 그 다음 줄부터 M www.acmicpc.net 풀이 단순한 BFS 문제 특정 구역에 텔레포트를 할 수 있는 구역을 설정한 뒤 해당 구역을 방문하면 텔레포트를 할 수 있게 하면 된다. 유의해야 할 점은 한 공간에 여러 곳을 텔레포트할 수도 있다는 것과, 텔레포트는 일방통행이 아닌 양방통행이라는 것이다. 이 코드같은 경우는 딕셔너리 안에 키는 장소, 값은 se..
문제 https://www.acmicpc.net/problem/18404 18404번: 현명한 나이트 첫째 줄에 N과 M이 공백을 기준으로 구분되어 자연수로 주어진다. (1 ≤ N ≤ 500, 1 ≤ M ≤ 1,000) 둘째 줄에 나이트의 위치 (X, Y)를 의미하는 X와 Y가 공백을 기준으로 구분되어 자연수로 주어진다. ( www.acmicpc.net 풀이 단순한 BFS 문제 나이트의 초기 위치부터 모든 위치를 탐색한 뒤, 저장해 두었던 상대편 말의 좌표값을 대입한 뒤 1을 빼고 출력한다. 제출 코드 # 2023/02/06 BFS # https://www.acmicpc.net/problem/18404 from collections import deque import sys input = sys.stdi..
문제 https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 풀이 주어진 금액을 만들 수 있는 모든 경우의 수를 출력하는 문제 반복문을 통해 현재 금액(j)에 현재 금액(j)에서 현재 단위(i)를 뺀 값을 더한다. (dp[j] += dp[j-i]) dp[0] = 1을 해야 시작을 1로 할 수 있다. 제출 코드 # 2023/02/04 DP # https://www.acmicpc.net/problem/9084 T = int(input())..
문제 https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 풀이 벽을 가장 적게 부수고, 목적지에 도착할때 부순 벽의 개수를 출력하는 문제 BFS를 이용해서 목적지에 도착할 때 visited에 부순 벽의 개수를 저장한다. 만약 다음 이동할 칸의 부순 벽의 횟수가 지금 부순 벽의 횟수보다 큰 경우 이동한다. 도착 지점의 인덱스 값 - 1을 출력하면 문제를 해결할 수 있다. 여담으로 해당 문제는 찾아보니 해결 방법이 여러 개가 있었는데, 첫번째로는 하얀..
문제 https://www.acmicpc.net/problem/12919 12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net 풀이 주어진 연산으로 S==T를 만들 수 있다면 1을 출력, 그렇지 않다면 0을 출력하는 쉬운 문제 처음엔 주어진 문제대로 코드를 제출해 보았지만(S를 T로 만들기) 시간초과가 발생하였다. 반대의 경우로 T를 S로 만드는 방법을 구현해 보았다. 제출 코드 # 2023/01/30 재귀 # https://www.acmicpc.net/problem/1291..
문제 https://www.acmicpc.net/problem/1938 1938번: 통나무 옮기기 첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4 ≤ N ≤ 50) 주어진다. 이어서 그 지형의 정보가 0, 1, B, E로 이루어진 문자열로 주어진다. 한 줄에 입력되는 문자열의 길이는 N이며 입력 문 www.acmicpc.net 풀이 시작 지점 "B"에서 도착 지점 "E"까지 도착하는데 걸리는 최소 횟수를 출력하는 문제 일단 각 지점의 중간 값을 구한 다음 도착 지점의 값과 시작 지점의 값이 같다면 정답을 출력하면 된다. 아래 기능만 구현할 수 있다면 문제를 해결할 수 있다고 생각한다. 현재 상태에서 이동할 수 있는 곳이 있다면 이동 현재 상태에서 회전할 수 있으면 회전 도착 여부 확인 및 정..
문제 https://www.acmicpc.net/problem/15961 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net 풀이 회전 초밥을 먹을 때 종류의 최대값을 구하는 문제 이전에 풀었던 [2531] 회전 초밥 문제(https://simple0710.tistory.com/10)와 같은 맥락이지만, 같은 코드로 제출할 경우 시간초과가 발생한다. 두 포인터와, 슬라이딩 윈도우 알고리즘을 사용한다. k 만큼의 구역을 설정하고 left 와 right 를 한칸씩 이동시키면..
문제 https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 풀이 회전 초밥을 먹을 때 종류의 최대값을 구하는 문제 집합 자료형(set)을 이용하여 중복된 번호가 없는 회전 초밥 데이터를 구하고, 쿠폰 번호에 해당하는 번호가 없는 경우 +1을 수행한 후, res 값과 비교한다. 굉장히 단순하다고 생각되는 풀이지만, k만큼의 리스트를 계속 만들어 내므로 시간 복잡도가 O(n * k) 이다. 이 방법 보다 더 좋은 ..
