[백준 / C++] N과 M (9)(실버2, 15663)

2024. 9. 19. 09:55·코딩테스트/백준 (Study)
목차
  1. 문제 풀이
  2. 코드
728x90
반응형

https://www.acmicpc.net/problem/15663

문제

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

  • N개의 자연수 중에서 M개를 고른 수열

입력

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

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

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

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

예제 입력 1

3 1
4 4 2

예제 출력 1

2
4

예제 입력 2

4 2
9 7 9 1

예제 출력 2

1 7
1 9
7 1
7 9
9 1
9 7
9 9

예제 입력 3

4 4
1 1 1 1

예제 출력 3

1 1 1 1

문제 풀이

이번 문제는 결과값이 중복되지 않고, 사전순으로 증가하는 수열들을 출력하는 문제입니다.

 

즉, 완전탐색 방식으로 모든 경우의 수를 체크하며 수열을 만들고, 수열의 크기가 m이 되는 순간 set 컨테이너를 확인해 중복이 아닌 경우 출력하는 방식으로 문제를 해결하게 되었습니다.

코드

더보기
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

int n, m;
vector<int> v;
set<vector<int>> s;
bool visited[9];

void Go(int cnt, vector<int> nums)
{
	if (nums.size() == m)
	{
		if (s.find(nums) == s.end())
		{
			for (int i : nums)
			{
				cout << i << " ";
			}
			cout << '\n';

			s.insert(nums);
		}

		return;
	}

	for (int i = 0; i < n; i++)
	{
		if (visited[i] == false)
		{
			visited[i] = true;
			nums.push_back(v[i]);

			Go(i + 1, nums);

			nums.pop_back();
			visited[i] = false;
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		int tempNum;
		cin >> tempNum;

		v.push_back(tempNum);
	}

	sort(v.begin(), v.end());

	vector<int>temp;
	Go(0, temp);
	
}

 

728x90
반응형
저작자표시 비영리 변경금지 (새창열림)

'코딩테스트 > 백준 (Study)' 카테고리의 다른 글

[백준 / C++] RGB거리(실버1, 1149)  (0) 2024.10.11
[백준 / C++] 1로 만들기(실버3, 1463)  (0) 2024.10.11
[백준 / C++] N과 M (8)(실버3, 15657)  (0) 2024.09.15
[백준 / C++] 스도쿠(골드4, 2580)  (0) 2024.09.12
[백준 / C++] N-Queen(골드4, 9663)  (0) 2024.09.11
  1. 문제 풀이
  2. 코드
'코딩테스트/백준 (Study)' 카테고리의 다른 글
  • [백준 / C++] RGB거리(실버1, 1149)
  • [백준 / C++] 1로 만들기(실버3, 1463)
  • [백준 / C++] N과 M (8)(실버3, 15657)
  • [백준 / C++] 스도쿠(골드4, 2580)
리태s
리태s
게임 클라이언트 프로그래머 직무를 준비하며 공부한 내용을 정리한 블로그입니다.
    반응형
    250x250
  • 리태s
    LeeTaes 공부노트
    리태s
  • 전체
    오늘
    어제
    • Home (165)
      • 프로젝트 (20)
        • Isaac 3D (5)
        • TimelessAdventure (13)
        • FruitsPuzzle (2)
      • Game Programming (25)
        • C# (8)
        • Unity Engine (6)
        • Unreal Engine (8)
        • UE_Multiplayer (3)
      • 코딩테스트 (111)
        • 프로그래머스 (Lv. 0) (27)
        • 프로그래머스 (Lv. 1) (31)
        • 프로그래머스 (Lv. 2) (21)
        • 백준 (Study) (29)
        • 알고리즘 (3)
      • CS지식 (7)
        • 운영체제 (7)
      • 일상 (2)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    fruitspuzzle
    2018 kakao
    프로그래머스
    Unreal Engine
    청년취업사관학교
    후기
    dataasset
    구현
    pcce 기출문제
    ai controller
    c#
    Summer/Winter Coding
    unrealengine
    CS지식
    project t.a develop
    코딩테스트
    프로젝트
    백준
    unity
    timelessadventure
    2022 kakao
    tsoftobjectptr
    Algorithm
    sesac
    fsoftobjectpath
    delegate
    2019 kakao
    C++
    issac3d
    프로세스
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
리태s
[백준 / C++] N과 M (9)(실버2, 15663)

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.