Algorithm/Backtracking15 ⚠️ 계란으로 계란치기 백준 16987번 계란으로 계란치기https://www.acmicpc.net/problem/16987 각 계란에는 내구도와 무게가 정해져 있다. 계란 A로 계란 B를 치는 경우 계란 A의 내구도 = 계란 A의 내구도 - 계란 B의 무게 계란 B의 내구도 = 계란 B의 내구도 - 계란 A의 무게 왼쪽에서부터 오른쪽으로 계란 A를 선택 (계란 A로 선택할 계란이 없거나 (모든 계란을 계란 A로 선택했거나), 계란 B로 선택할 계란이 없으면 종료) def backTracking(eggList, idx, count): global brokenCounter # 모든 계란을 부딪혔다면 현재까지 깨진 계란 수를 갱신 if idx == len(eggList): brokenCounter = .. 2024. 11. 12. 소문난 칠공주 백준 1941번 소문난 칠공주https://www.acmicpc.net/problem/1941 5 x 5 배열로 자리배치 (총 25) S와 Y로 구성돼 있음 완성된 리스트의 길이는 7이어야 한다 S >= 4여야 한다 원소들은 배열 내 가로나 세로로 인접해 있어야 한다 5 x 5 배열 내에서 조합할 수 있는 모든 7개의 원소 리스트를 체크한다원소 리스트가 가로와 세로로만 인접해 있다면 count += 1 import sysfrom itertools import combinationsfrom collections import dequeinputArray = [list(sys.stdin.readline().strip()) for _ in range(5)]count = 0dx = [0, 0, -1, 1]dy =.. 2024. 8. 27. 암호 만들기 백준 1759번 암호 만들기https://www.acmicpc.net/problem/1759 비밀번호의 총 개수는 L개, 알파벳의 증가순으로 나열돼 있다 C개의 알파벳이 주어졌을 때, 사전식으로 가능성이 있는 암호를 모두 출력 최소 한 개의 모음과 최소 두 개의 자음으로 구성돼야 한다 모음 구별을 위해 모음만 담은 리스트를 따로 만들었다passwordArray의 길이가 L을 충족할 때, passwordArray 내 모음의 개수를 알아내고L - 모음의 개수로 자음의 개수를 알아낸다 + sort() 함수는 알파벳도 사전순으로 정렬해준다+ join 함수는 문자열 리스트를 문자열로 출력 import sysL, C = map(int, sys.stdin.readline().split())array = sys.std.. 2024. 8. 26. 로또 백준 6603번 로또https://www.acmicpc.net/problem/6603 수를 6번 골라야 하니 backTracking 함수에서 리스트를 출력하는 조건을리스트의 길이가 6일 때로 설정한다 k와 s를 한 줄로 입력받으니리스트 하나로 입력받은 후, k와 s로 잘라서 저장한다 중복된 수를 고르면 안 되니 backTracking의 매개변수 중 for문의 실행 범위를 정하는 start 변수에 i + 1 값을 넘겨준다 import sysdef backTracking(start, k, s): if len(selected) == 6: print(" ".join(map(str, selected))) return for i in range(start, k): .. 2024. 8. 25. N과 M (10), (11), (12) 백준 15664번 N과 M (10)https://www.acmicpc.net/problem/15664 N과 M (9)번 문제와 같이 깊이 별로 이전에 사용했던 수와 동일한 수를 사용하는지 체크해서 풀었다(10)번 문제는 비내림차 순이라는 조건이 있으니 used 리스트를 사용하지 않고 backTracking 함수를 재귀 호출할 때 매개변수로 i + 1 값을 준다 import sysN, M = map(int, sys.stdin.readline().split())array = list(map(int, sys.stdin.readline().split()))array.sort()selected = []def backTracking(start): if len(selected) == M: print.. 2024. 8. 24. N과 M (9) 백준 15663번 N과 M (9) N 개의 자연수 중에서 M개를 고른 수열N 개의 자연수 중에는 중복하는 수가 있는데, 중복되는 수열을 출력해서는 안 된다 : 수열을 저장하는 리스트를 만든다 수열의 길이가 M이 되면, 수열을 저장하는 리스트 중 일치하는 리스트가 있는지 체크한다 일치하는 리스트가 없다면 수열을 저장하는 리스트에 해당 리스트를 추가한 후 print한다 수열 안에서 N 개의 수를 나열하는 조건은 없지만 수열을 나열하는 조건은 사전 순으로 증가하는 순서이다 그래서 used 리스트를 만들어서 수열 안에서 해당 수를 사용했는지 체크했다 import sysN, M = map(int, sys.stdin.readline().split())array = list(map(int, sys.stdin.read.. 2024. 8. 24. N과 M (8) 백준 15657번 N과 M (8)https://www.acmicpc.net/problem/15657 N 개의 자연수는 모두 다른 수 그 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 되는데, 고른 수열은 비내림차순이어야 한다 = 자기 자신의 인덱스 번호를 backTracking 함수의 매개변수로 전달함으로서 달성 그럼 중복 선택의 조건도 달성하고, N 개의 자연수를 입력받고 sort() 한다면 비내림차순으로 정렬할 수 있다 + 수열이 사전 순으로 증가하는 순서로 출력할 수 있음 import sysN, M = map(int, sys.stdin.readline().split())array = list(map(int, sys.stdin.readline().split()))array.sort()select.. 2024. 8. 23. N과 M (7) 백준 15656번 N과 M (7)https://www.acmicpc.net/problem/15656 중복을 허용하되,수열들의 나열이 사전 순으로 증가하는 순서여야 한다 (1 1 다음엔 1 7이 출력되야 하는 것) sort와 range만 이용해서 구현 가능하다 ! import sysN, M = map(int, sys.stdin.readline().split())array = list(map(int, sys.stdin.readline().split()))array.sort()selected = []def backTracking() : if len(selected) == M : print(" ".join(map(str, selected))) return for i i.. 2024. 8. 19. N과 M (6) 백준 15655번 N과 M (6)https://www.acmicpc.net/problem/15655 고른 수열은 오름차순이어야 하며, 중복이 있어선 안 된다N과 M 문제 중에 array의 요소만 다르고 조건(👆)은 같은 문제가 있어서 바로 풀 수 있었다 ! import sysN, M = map(int, sys.stdin.readline().split())array = list(map(int, sys.stdin.readline().split()))array.sort()selected = []def backTracking(start) : if len(selected) == M : print(" ".join(map(str, selected))) return for .. 2024. 8. 19. 이전 1 2 다음
