https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 풀이 # 7562번 나이트의 이동 # 배열의 크기는 가로, 세로가 I. 시작점, 목표점이 주어짐, 이동방향은 나이트의 이동 8개 # bfs는 최적의 수를 주기에 visited 안에서 이동할때마다 1씩 추가해준다. import sys from collections import deque input = sys.stdin.readline dx = [2, 2, -2, -2, -1, 1, -1, 1] dy ..

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 풀이 # 2468번 안전영역 # 크기가 N인 정사각형, 시작지점 없음 직접 찾아야함 최소 높이와 최대 높이 구하기 # 배열은 graph, visited로 구분 import sys from collections import deque input = sys.stdin.readline def bfs(height, k, j): queue = deque() queue.append((k,j)) while queue..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 좌표문제는 주로 dfs로 문제를 푸는 편이다 이동할 수 있는 경우의 수를 따로 리스트에 담아둔 뒤 BFS로 모든경우의 수를 계산해서 graph에 저장해준다. # 1697번 숨바꼭질 # 시작값과 목표값도 주어짐 배열 한계는 0 - 100000 까지 # 이동방향은 3가지 [+1, -1, 이전값*2], 최적의 거리를 찾기에 bfs사용 import sys from coll..

https://www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 풀이 단순한 그리디 문제이기에 문재의 설명에 맞게 써주면된다. # 13456번 시험감독 # 총감독관, 부감독관 사람 수 파악하 import sys input = sys.stdin.readline test = int(input()) # 시험장 개수, int화 시켜서 줄 개행(이스케이프 코드) 제거 students = list(map(int, ..

https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 풀이 BFS로 모든경우의 수를 visit에 저장해준 뒤 target값을 출력 # 5014번 스타트링크 from collections import deque floor, start, target, u, d = map(int, input().split()) visit = [0] * (floor+1) visit[0] = 1 dx = [u, -d] def bfs(): queue = deque() queue.appen..

https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 풀이 방향키로만 목표값인 n에 가는것을 초깃값으로 잡아준 뒤 0~1000000까지의 숫자 중 만들 수 있는 숫자들을 완전탐색하여 최솟값이 나올 수 있게 계속 비교해준다. 0

https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 풀이 라이브러리 itertools의 combinations(조합)을 사용하여 풀어주었다. # 6603번 로또 from itertools import combinations as comb while True: numbers = input().split() if numbers[0] == '0': break else: numbers = numbers[1:] for i in comb(numbe..

https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 풀이 시작값과 목표값이 각 테스트케이스마다 주어진다. 시작값의 각 자리의 숫자를 바꿔가면서 소수를 유지하면서 목표값으로 바꿀 수 있는가? 1, 에라토스테네스의 체 알고리즘으로 1000 ~ 9999까지의 숫자들 중 소수만 뽑아서 리스트를 만들어준다.2, BFS를 실행해서 숫자의 각 자리를 1~9까지의 숫자로 바꿔가면서 목표값까지 이동할 수 있나 없나 확인한다.대신 첫방문이며 소수여야하고 1000이상인 숫자여..