즐겁게, 코드

[백준 온라인 저지 링크] 2992번: 크면서 작은 수 정수 X가 주어졌을 때, X와 구성이 같으면서 X보다 큰 수 중 가장 작은 수를 출력한다. 수의 구성이 같다는 말은, 수를 이루고 있는 각 자리수가 같다는 뜻이다. 예를 들어, 123과 321은 수의 구성이 www.acmicpc.net 간단한 브루트 포스 문제처럼 보일 수 있지만, N과 M 유형의 백트래킹 문제입니다. 주어진 수와 동일한 구성이면서 해당 수보다 처음으로 큰 숫자를 찾아야 하는데요, 여기서 동일한 구성의 수라 함은 각 자리수를 구성하는 수를 재배열해 만들 수 있는 수를 의미합니다. 즉, 주어진 수가 176이라면 671이 167과 "구성이 같은 수" 이자 첫 번째로 큰 수가 됩니다. 입력값이 1 ~ 999,999라고 해서 브루트 포스로 ..

[문제 링크] - https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 백트래킹 문제입니다. 한 가지 주의할 점이 있다면, 만약 부분수열의 누적합을 갖는 변수를 0으로 초기화하고, 만들어야 하는 정수가 0일 때 다음과 같이 로직을 작성할 수 있습니다. def backtrack(idx, numberSum): global count if idx == N: return if numberSum == S: count += ..

[문제 링크] - https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net N과 M 유형의 백트래킹 문제입니다. 단, 중복된 수를 뽑아서는 안되며 로또번호를 오름차순으로 나열해야 한다는 점만 유의하시면 되는 문제입니다. 정답 코드 (Python) S = [] lottery = [0] * 13 visited = [] def backTrack(depth): global S if depth == 6: for i in range(6): print(l..

[백준 온라인 저지 링크] 16922번: 로마 숫자 만들기 2, 6, 10, 11, 15, 20, 51, 55, 60, 100을 만들 수 있다. www.acmicpc.net 로마자 조합의 순서를 따지지 않는다는 조건을 통해 중복조합을 구하는 문제임을 알 수 있는데요, 따라서 N과 M 4번과 형태가 매우 유사하지만 같은 코드로 풀면 N=6 부터 답이 달라지기 시작합니다. 왜냐하면 바로 "조합의 합이 같은 경우" 가 생기기 때문인데요, 한번 예시를 들어보겠습니다. // N(뽑아야 하는 수)이 2일 때 (N과 M) => (로마자) 1 1 I I (2) 1 2 I V (6) 1 3 I X (11) 1 4 I L (51) 2 2 V V (20) 2 3 V X (15) 2 4 V L (55) 3 3 X X (20)..