다시푸는 코딩 테스트 준비 일지
응시 사이트 : BOJ
문제 : 15657.N과 M(8)
사용언어 : C#
난이도 : Middle
풀이시간 : 38m
유형 : 백트래킹 , DFS
문제
N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.
N개의 자연수 중에서 M개를 고른 수열
같은 수를 여러 번 골라도 된다.
고른 수열은 비내림차순이어야 한다.
길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.
입력
첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
예제 입력 1 복사
3 1
4 5 2
예제 출력 1 복사
2
4
5
예제 입력 2 복사
4 2
9 8 7 1예제 출력 2 복사
1 1
1 7
1 8
1 9
7 7
7 8
7 9
8 8
8 9
9 9예제 입력 3 복사
4 4
1231 1232 1233 1234예제 출력 3 복사
1231 1231 1231 1231
1231 1231 1231 1232
1231 1231 1231 1233
1231 1231 1231 1234
1231 1231 1232 1232
1231 1231 1232 1233
1231 1231 1232 1234
1231 1231 1233 1233
1231 1231 1233 1234
1231 1231 1234 1234
1231 1232 1232 1232
1231 1232 1232 1233
1231 1232 1232 1234
1231 1232 1233 1233
1231 1232 1233 1234
1231 1232 1234 1234
1231 1233 1233 1233
1231 1233 1233 1234
1231 1233 1234 1234
1231 1234 1234 1234
1232 1232 1232 1232
1232 1232 1232 1233
1232 1232 1232 1234
1232 1232 1233 1233
1232 1232 1233 1234
1232 1232 1234 1234
1232 1233 1233 1233
1232 1233 1233 1234
1232 1233 1234 1234
1232 1234 1234 1234
1233 1233 1233 1233
1233 1233 1233 1234
1233 1233 1234 1234
1233 1234 1234 1234
1234 1234 1234 1234문제 풀이 접근
이 문제의 조건은
1. 같은 수를 여러번 고르는 것이 가능
2. 비 내림차순 => A1,A2,A3,A4 가 있다면, A1<=A2<=A3<=A4
예를들면 1 3 5 7 이 있다. 4개중에 2개 뽑는다.
가능 )
1 3
1 5
1 7
3 3
3 5
3 7
5 5
5 7
7 7
불가능 )
3 1
3 3
5 1
5 3
7 1
7 3
7 5
이렇듯, 앞의 수보다 크거나 같은 조건을 가진 수열을 의미한다.
내가 생각한 방법은 BT 내부에서 for 문으로 Arr의 인덱스 0부터 Length 까지 순회한다.
0회 차 일때 Prev의 값이 비교할 것이 없기 때문에, 자연수라는 조건으로 0회차 에서는 -1을 Prev 값으로 넘겨준다.
이후 Prev 값은 BT 함수를 타고 들어가 내가 함수를 타고 들어온 Prev 값보다 순회하는 인덱스의 참조값인 _arr[i] 의 값보다 이전에 가지고온 값을 비교하여 Prev 보다 작다면 Continue 하는 방식으로 조건을 걸어주었더니, 문제에서 요구하는 비 내림차순으로 수열을 구성할 수 있었다.
이외로 이 문제는 M과N (7)번 문제와 제한 시간이 동일한데, 시간초과가 안떠서 조금 놀랐다.
작성 코드 (C#)
using System;
using System.Collections.Generic;
using System.Globalization;
using System.Linq;
using System.Text;
/////*
//// * Difficulty : Middle
//// * URL : https://www.acmicpc.net/problem/15657
//// * Time : 38h
///
/// BOJ_15657_N과 M (8)
//// */
///
namespace CodingTestProj
{
internal class Program
{
static void Main(string[] args)
{
Solution solution = new Solution();
solution.solve();
}
}
public class Solution
{
public const int _max = 8;
public int _n;
public int _m;
public int[] _arr;
public int[] _per;
public StringBuilder _sb;
public void solve()
{
_sb = new StringBuilder();
string[] _in = Console.ReadLine().Split(' ');
_n = int.Parse(_in[0].ToString());
_m = int.Parse(_in[1].ToString());
_in = Console.ReadLine().Split(' ');
_arr = new int[_n];
for (int i = 0; i < _in.Length; ++i)
_arr[i] = Int32.Parse(_in[i]);
List<int> _tempInt = new List<int>(_arr);
_tempInt.Sort(Sorted);
_arr = _tempInt.ToArray();
_per = new int[_m];
BT(0, ref _per, 0, 0,-1);
Console.Write(_sb.ToString());
}
public int Sorted(int n, int m)
{
return n.CompareTo(m);
}
public void BT(int pos, ref int[] c, int cnt, int depth, int prev)
{
if (cnt >= _m)
{
for(int i = 0; i < cnt; ++i)
{
_sb.Append(c[i]);
if(i != cnt - 1)
_sb.Append(" ");
}
_sb.AppendLine();
}
else if (pos == _arr.Length) return;
else
{
for (int i = 0; i < _arr.Length; ++i)
{
if (_arr[i] < prev) continue;
c[pos] = _arr[i];
BT(pos+1, ref c, cnt + 1, depth + 1, _arr[i]);
}
}
}
}
}코드 결과
