[백준 baekjoon] N과 M 모든 유형 뽀개기 - Java

순열

1. 순열

서로 다른 n개에서 r개를 택해 일렬로 나열하는 것

• 문제

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

  • 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
  • 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

• 풀이법
  • visit[] 배열 사용 : 중복되어 저장되는지를 체크한다.
  • 0 <= i < n : 비내림차순 정렬 X
  • if(!visit[i]) 일 때 arr[depth] 에 값을 저장
  • if (depth == r) 이 되면 arr의 값을 문제의 조건에 맞게 처리하고 return한다.

2. 중복 순열

서로 다른 n개에서 중복을 허락하여 r개를 택해 일렬로 나열하는 것

• 문제

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

  • 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
  • 1부터 N까지 자연수 중에서 M개를 고른 수열
  • 같은 수를 여러 번 골라도 된다.

• 풀이법
  • 이미 사용한 값을 중복해서 사용해도 상관 없다.
    • visit[] 배열 사용 X
    • if(!visit[i]) 확인 X
  • 0 <= i < n
    • 비내림차순 정렬 X
  • arr[depth] 에 값을 저장
  • if (depth == r) 이 되면 arr의 값을 문제의 조건에 맞게 처리하고 return한다.

3. 같은 것이 있는 순열

• 경우의 수

  • n개 중에 같은 것이 각각 p개, q개, ... , r개씩 있을 때 이들을 모두 일렬로 나열하는 순열의 수는

      n! / (p! * q! * r!) (단, p+q+...+r = n)

• 문제

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

  • N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
  • N개의 자연수 중에서 M개를 고른 수열
  • N개의 자연수에는 서로 같은 수가 존재할 수 있다.

• 풀이법

4. 같은 것이 있는 중복 순열

• 문제
  https://www.acmicpc.net/problem/15665
  N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

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

• 풀이법

  • before 변수 사용
    • 이전에 탐색한 노드의 값을 저장한다.
    • 현재 탐색하려는 노드의 값이 이전에 탐색한 노드의 값 (before)과 같은지를 체크한다.
    • 만약 같다면, 뒤이어 만들어질 수열은 직전에 만든 수열과 같다. 중복되는 수열이 있으면 안되기 때문에 이 경우를 건너뛰고 탐색을 진행한다.
    • 다를 경우에만 arr[depth] 에 현재 노드의 값을 저장한다.
  • HashSet을 이용해볼까?
  • 0 <= i < n
    • 비내림차순 정렬 X
      • ex) 91과 19를 다르게 count한다.
  • if (depth == r) 이 되면 arr의 값을 문제의 조건에 맞게 처리하고 return한다.

조합

1. 조합

서로 다른 n개에서 r개를 택하는 것

• 문제
  https://www.acmicpc.net/problem/15650
  • 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
  • 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
  • 고른 수열은 오름차순이어야 한다.
• 풀이법

2. 중복 조합

서로 다른 n개에서 중복을 허락하여 r개를 택하는 것

• 경우의 수

  • 2개의 문자 a, b에서 중복을 허락하여 3개를 택하는 조합은 aaa, aab, abb, bbb 4가지이다.

• 문제
  https://www.acmicpc.net/problem/15652

  • 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
  • 같은 수를 여러 번 골라도 된다.
  • 1부터 N까지 자연수 중에서 M개를 고른 수열
  • 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

• 풀이법

3. 같은 것이 있는 조합

• 문제
  https://www.acmicpc.net/problem/15664

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

  • N개의 자연수 중에서 M개를 고른 수열
  • 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

• 풀이법

4. 같은 것이 있는 중복 조합

• 문제
  https://www.acmicpc.net/problem/15666

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

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

• 풀이법

  • before 변수 사용
    • 이전에 탐색한 노드의 값을 저장하고 현재 탐색하려는 노드의 값과 비교한다.
    • 다를 경우에만 arr[depth] 에 현재 노드의 값을 저장한다.
  • cnt <= i < n
    • 비내림차순 정렬 O
    • 현재 노드의 값을 사용했다면 이전 노드의 값은 탐색할 필요가 없다.
  • if (depth == r) 이 되면 arr의 값을 문제의 조건에 맞게 처리하고 return한다.

정리

유형이 많아서 시간을 들여서 정리를 해보았다. 헷갈리지 않게 틈틈이 복습하자!