시나위

https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 손 풀 겸 푼 문제. 백트래킹을 사용해서 모든 조합을 만들어내면 된다. 조건이 별로 걸지 않아서 dfs와 차이가 없다. visit = None numbers = None ans = None def backtrack(ind, limit, total, prev): global visit, numbers, ans if ind == limit: ans = max(ans, total) return for i in ran..

https://www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 모든 값을 탐색하면서 이전보다 큰 값인 경우에만 백트래킹하는 방법으로 풀었다. desc_nums = [] visit = [False for _ in range(10)] def make_number(visit): ret = 0 for i in range(9, -1, -1): if visit[i]: ret = ret * 10 + i return ret def backtrack(ind=-..

https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 시뮬레이션을 요구하는 삼성 느낌의 기출이다. 주어진 조건대로 만들어주기만하면 되는데 그게 너무 오래걸리는 문제여서 구현이 오래걸렸다. 완전탐색으로 맵에 그렸다가 지웠다를 반복하면 값이 나온다. import sys; input = sys.stdin.readline answer = None N, M = None, None cctv_list, d_map, r_map = None, None, ..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net import sys; input = sys.stdin.readline def backtrack(r, c): global answer # 1 길이 갱신 answer = max(answer, len(alphabet)) # 2 탐색 for i in range(4): nr = r + dr[i] nc = c + dc[i] if 0

www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net import sys input = sys.stdin.readline want_ch = input().rstrip() want_ch_list = list(map(int, list(want_ch))) want_ch = int(want_ch) use_set = set(range(10)) M = int(input()) if M: crashed_set = set(map(int, input().split(..

www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net delta = [(-1, 0), (1, 0), (0, -1), (0, 1)] def backtrack(inboard, inred, inblue, ind=0): global result, cnt, delta # if result == 1: # return if ind == 10: return else: for i in range(4): tmp_board = [in..

www.acmicpc.net/problem/13459 13459번: 구슬 탈출 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net delta = [(-1, 0), (1, 0), (0, -1), (0, 1)] def backtrack(inboard, inred, inblue, ind=0, arr=[]): global result, delta if result == 1: return if ind == 10: return else: for i in range(4): tmp_board = [inboa..

www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net matrix = [input() for _ in range(5)] delta = [(-1, 0), (1, 0), (0, -1), (0, 1)] result_set = set() def backtrack(arr, index=0, S=0, Y=0): tmp = arr if Y > 3: return if index == 6: arr.sort() result_set.add(tuple(arr)) else: adjacents..

www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net number_set = set() matrix = [list(map(int, input().split())) for _ in range(5)] delta = [(-1,0),(1,0),(0,-1),(0,1)] def backtrack(x,y, index=0, string=''): if index == 5: number_set.add(string) else: for i i..

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf&categoryId=AV4suNtaXFEDFAUf&categoryType=CODE&problemTitle=SW&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=3 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com import sys sys.stdin = open('./sample_input_1.txt', 'r') for tc in range(1, int(input()) +..