본문 바로가기

Algorithm 💡/Backtracking14

[백준 2239번] 스도쿠 https://www.acmicpc.net/problem/2239import sysinput = sys.stdin.readline# 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에# 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다# 하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성# 9개의 줄에 9개의 숫자로 보드가 입력된다. # 아직 숫자가 채워지지 않은 칸에는 0이 주어진다.# 9개의 줄에 9개의 숫자로 답을 출력# 답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력# 즉, 81자리의 수가 제일 작은 경우를 출력한다.area = [list(map(int,list(input().rstrip()))) for _ in range(9.. 2024. 10. 28.
[백준 18428번] 감시 피하기 https://www.acmicpc.net/problem/18428import sysimport copyinput = sys.stdin.readline# NxN 크기의 공간에 선생님(T), 학생(S), 혹은 장애물(O)이 위치# 복도로 빠져나온 학생들은 선생님의 감시에 들키지 않는 것이 목표# 각 선생님들은 자신의 위치에서 상, 하, 좌, 우 4가지 방향으로 감시를 진행# 선생님은 상, 하, 좌, 우 4가지 방향에 대하여, 아무리 멀리 있더라도 장애물로 막히기 전까지의 학생들은 모두 볼 수 있다# 단, 복도에 장애물이 위치한 경우, 선생님은 장애물 뒤편에 숨어 있는 학생들은 볼 수 없다# 학생들은 복도의 빈 칸 중에서 장애물을 설치할 위치를 골라, 정확히 3개의 장애물을 설치# 결과적으로 3개의 장애물을.. 2024. 10. 5.
[백준 6603번] 로또 https://www.acmicpc.net/problem/6603import sysinput = sys.stdin.readline# {1, 2, ..., 49}에서 수 6개를 고른다# 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것def combinations(arr, k): cases = [] def dfs(elements,index): if len(elements) == k: cases.append(elements) return for i in range(index+1,len(arr)): dfs(elements+[arr[i]],i) dfs([].. 2024. 10. 3.
[백준 16987번] 계란으로 계란치기 https://www.acmicpc.net/problem/16987import sysinput = sys.stdin.readline# 각 계란에는 내구도와 무게가 정해져있다# 계란으로 계란을 치게 되면 각 계란의 내구도는 '상대 계란의 무게'만큼 깎이게 된다# 그리고 내구도가 0 이하가 되는 순간 계란은 깨지게 된다# 일렬로 놓여있는 계란에 대해 왼쪽부터 차례로 들어서 한 번씩만 다른 계란을 쳐 최대한 많은 계란을 깨는 문제# 1. 가장 왼쪽의 계란을 든다.# 2. 손에 들고 있는 계란으로 깨지지 않은 다른 계란 중에서 하나를 친다.# (단, 손에 든 계란이 깨졌거나 깨지지 않은 다른 계란이 없으면 치지 않고 넘어간다.)# 3. 가장 최근에 든 계란의 한 칸 오른쪽 계란을 손에 들고 2번 과정을 다시 진.. 2024. 7. 12.
[백준 1941번] 소문난 칠공주 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net from itertools import combinations from collections import deque dx = [-1,1,0,0] dy = [0,0,-1,1] area = [list(input()) for _ in range(5)] positions = [] for i in range(5): for j in range(5): positions.append((i,j)) combs = list(combinations(positions,7)) answer .. 2023. 11. 22.
[백준 1182번] 부분수열의 합 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net n, s = map(int,input().split()) # N개의 정수로 이루어진 수열, 부분수열의 원소를 다 더한 값이 S가 되는 경우의 수 data = list(map(int,input().split())) count = 0 visited = [False]*n def dfs(total,index,depth): global count if total == s and depth != 0: count += 1 for i in .. 2023. 10. 20.

티스토리툴바