로또

문제

독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다.

로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.

예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])

집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 주어진다.

입력의 마지막 줄에는 0이 하나 주어진다. 

출력

각 테스트 케이스마다 수를 고르는 모든 방법을 출력한다. 이때, 사전 순으로 출력한다.

각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

이번 문제는 조합의 응용 문제인 로또 문제를 풀어 보겠습니다.

이전 n과m(2)에서의 입력 조건은 N 이 주어 졌을때 1, 2, 3, .... N 이 범위라면

이번에는 n의 범위를 직접 입력해서 6개를 중복 없이 뽑는 경우의 수 입니다.

* 0이 입력될때까지 무한 반복

* while 실행시 사용했던 배열 초기화가 이루어져야 합니다.

연산자 끼워넣기

문제

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.

우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.

예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.

• 1+2+3-4×5÷6
• 1÷2+3+4-5×6
• 1+2÷3×4-5+6
• 1÷2×3-4+5+6

식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.

• 1+2+3-4×5÷6 = 1
• 1÷2+3+4-5×6 = 12
• 1+2÷3×4-5+6 = 5
• 1÷2×3-4+5+6 = 7

N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. 

출력

첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다. 연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

이번 문제는 연산자 끼워넣기 dfs, backtracking 문제입니다.

숫자의 개수는 N 개 연산자의 개수는 N-1개 이고 연산자의 우선순위는 맨 처음부터 입니다.

생각보다 간단? 하게 풀 수 있는 문제 이지만 여기서 주의깊게 확인해야 할 부분은 출력 에 나와 있는 -10억 ~ 10억 이라는 범위 입니다.

생각 없이 result1에 최댓값을 넣기 위해 0으로 초기화 하고 result2에는 1e9로 했다가 10분동안 에러 찾으려고 고생했네요.

이럴때 -10억 -1 , +10억 +1 로 초기화 할 수 있지만 c++ 에는 limits 이나 limits.h 에 INT_MAX, INT_MIN 을 이용할 수 있습니다.

코드는 다음과 같습니다.

N과 M (4)

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

지금까지 순열, 조합, 중복 순열을 알아봤습니다.

마지막으로 중복 조합에 대해서 공부해 보겠습니다.

중복 조합에서는 next 인자의 값을 증가시키지 않고 전달하여 for문에서 다시 i=next 부터 찾도록? 구현해보았습니다.

N과 M (3)

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

이번 문제는 중복을 허용하는 순열(duplicate permutation) 입니다.

중복을 허용하기 때문에 일반 순열(permutation) 보다 구현하기 좀 더 쉽습니다.

저는 첫 번째 원소는 0으로 선언하여 구현하는 것을 선호하여 0 ~ n-1 까지의 경우의 수를 구한 뒤 출력할떄 +1을 해주었습니다.

N과 M (2) 성공분류

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

이번 문제는 저번 문제의 순열 문제에 이어서 조합 문제 입니다.

N개의 원소중에서 R개의 원소를 중복없이 뽑는 알고리즘 입니다.

문제 해결 방법으로는 dfs 를 이용하였습니다.

dfs(int depth, int value) 형식으로 깊이가 증가할수록 value의 값을 업데이트 하였습니다.

문제

8

92

backtracking의 첫 문제는 n-queen 문제로 정했습니다.

n x n 의 행렬에 대각선, 가로, 세로가 겹치지 않도록 모든 행에 말을 두어 그 경우의수를 출력하는 문제입니다.

풀이 순서는 다음과 같습니다.

1. 모든 행에 말 배치하기

2. 가로 세로 대각선이 겹치지 않는다면 말을 두기

3. 모든행의 말을 두었다면 결과값 업데이트

코드