본문 바로가기
728x90

백트래킹12

[python] 백준 1062 가르침 https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 문제해결 anta와 tica 사이 알파벳을 봐야하지만 중요한 것은 'a', 'n', 't', 'i', 'c' 는 무조건 들어가야한다. 즉 k=5: learned = [0]*123 for x in {'a','n','t','i','c'}: learned[ord(x)] = 1 for teach in list(combinations(res,k-5)): for t in teach: learned[o.. 2023. 5. 5.
[python] 백준 1799 비숍 https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 문제 해결 비숍을 하나 자리에 놓을 때 우상향 대각선, 우하향 대각선 두가지 위치에 비숍이 있는지 없는지 확인해야한다. 우상향 대각선을 두고 자리를 위치시켜가며 배열 시킬 때 우하향 대각선 어디에 비숍이 있는지는 중요하지 않다. 다만 있는지 없는지가 중요하다. dictionary를 통해 몇 번째 우하향 곡선에 비숍의 유무(0,1)로 확인하므로 둘 수 있는지 없는지를 확인한다. CODE import sys .. 2023. 4. 20.
[python] 백준 16987 계란으로 계란치기 https://www.acmicpc.net/problem/16987 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 문제 해결 전형적인 백트래킹 문제 하나씩 차례로 부딪힐 수 있는 것을 부딪히고 다음 것을 부딪히고 하다가 끝까지 간후 다시 부딪히기 전으로 합치고 다음 것부터 부딪히고 모든 경우의 수를 계산해야한다. CODE n = int(input()) S = [] for _ in range(n): a, b = map(int, input().split()) S.append([a,b]) def df.. 2023. 4. 18.
[python] 백준 1941 소문난 칠공주 https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 문제해결 조건이 4가지를 만족해야하므로 차례대로 만족시킬 수 있는 방법이 뭔지 생각해본다. 1번과2번조건을 묶고 3번과 4번 조건을 묶으면 좋다. 7명의 여학생으로 구성되어있어야하므로 depth=7인 dfs를 사용하면 좋을 것 같다. (게다가 가로 또는 세로로 인접해 있어야하므로 dfs로 이동하는 것은 좋다.) 임도연파가 4명 이상이면 안되는 것이기 때문에 중간에 그만두고 다른 것을 찾도록 한다. b.. 2023. 4. 18.
728x90