개발 다이어리

경우의 수, nCr는 (n-1Cr-1)+ (n-1Cr) 와 같다는 공식을 사용한다.

n은 요소의 개수, r은 그 중 몇 개 선택할지

그리고 n==r 인 경우 경우의 수는 1, 요소가 3개에 3개를 선택한다면 경우의 수는 1개 뿐

r==0 인 경우도 경우의 수는 1이다, 요소가 아무리 많아도 0개를 선택할 경우의 수는 1개 뿐

6C4는 15의 경우의 수가 나온다.

코드

class 조합의경우수$메모이제이션{
	static int[][] dy=new int[35][35];
	static int cnt1,cnt2;
	
	static int DFS1(int n, int r){
		cnt1++;
		if(n==r || r==0) return 1;
		else return DFS1(n-1, r-1)+DFS1(n-1, r);
	}
	
	static int DFS2(int n, int r){
		cnt2++;
		if(dy[n][r]!=0) return dy[n][r]; //이미 계산해놓은게 있다.
		if(n==r||r==0) return 1;
		else {
			return dy[n][r]=DFS2(n-1,r-1)+DFS2(n-1,r);
		}
		
	}
	
	public static void main(String[] args){
		int n=6;
		int r=4;
		
		System.out.print("메모이제이션 사용 안함 ");
		System.out.println(DFS1(n, r)+" "+cnt1);
		System.out.print("메모이제이션 사용 함 ");
		System.out.println(DFS2(n, r)+" "+cnt2);
	}
}

결과

메모이제이션 사용 안함 15 29
메모이제이션 사용 함 15 17

숫자가 적어서 메모이제이션 효과가 미미해보이지만 아래처럼 조금만 증가해도 기하급수적으로 반복호출하게 된다.

메모이제이션 사용 안함 30045015 60090029
메모이제이션 사용 함 30045015 401

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42578

스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.

예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.

종류 이름

스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
• 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.
• 같은 이름을 가진 의상은 존재하지 않습니다.
• clothes의 모든 원소는 문자열로 이루어져 있습니다.
• 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.
• 스파이는 하루에 최소 한 개의 의상은 입습니다.

입출력 예

입출력 예 설명

예제 #1
headgear에 해당하는 의상이 yellow_hat, green_turban이고 eyewear에 해당하는 의상이 blue_sunglasses이므로 아래와 같이 5개의 조합이 가능합니다.

1. yellow_hat
2. blue_sunglasses
3. green_turban
4. yellow_hat + blue_sunglasses
5. green_turban + blue_sunglasses

예제 #2
face에 해당하는 의상이 crow_mask, blue_sunglasses, smoky_makeup이므로 아래와 같이 3개의 조합이 가능합니다.

1. crow_mask
2. blue_sunglasses
3. smoky_makeup

코드

import static java.util.stream.Collectors.*;

import java.util.Map;
import java.util.stream.Stream;

class Solution {
	public int solution(String[][] clothes) {
		Map<String, Integer> collect = Stream.<String[]>of(clothes)
			  .collect(groupingBy( strArr->strArr[1], //[1]은 종류
					  collectingAndThen(reducing(0L, e -> 1L, Long::sum )
                      					, Long::intValue)));
		
		return collect.values().stream().reduce(1, (a,b) -> a*(b+1) )-1;
        // 각 부위별 +1 은 옷을 안입는 경우의 수이다. 
        // 마지막 -1은 반드시 옷은 1개 이상은 입는 다는 조건이 있기 떄문이다.
	}
}

결과

아흙.... 간단한 수학공식인데 기억이 안 나서 공식을 검색해보고 작성했다.

수포자였어도 이 정도는 아니었는데....

위 문제의 경우 경우의 수는 다음과 같다.

각 부위 별 옷의 수 + 1  

각 부위 별 옷의 수 곱 이후  -1

각 부위별 +1 은 옷을 안 입는 경우이다.

각 부위별 옷의 수를 전부 곱한 후 -1은 조건 중에 "스파이는 하루에 최소 한 개의 의상은 입습니다."를 보정한 값이다.