[백준] 16968번 차량 번호판1 조합을 활용하여 간단하게 해결해보기 : Programming Story

1. 문제

www.acmicpc.net/problem/16968

문제는 위의 링크에 들어가면 확인해볼 수 있다.

2. 풀이

이 문제를 푸는 여러 방법이 있을 수 있는데 오늘 여기서는 재귀로 푸는 법 말고 조합을 활용해서 쉽게 풀 수 있는 법을 소개해보도록 하겠다.

조합을 활용한다는 것은 각 자리의 가능한 경우의 수를 계산해서 곱해준다는 것이다.

만약 해당 자리의 알파벳이 'c'라면 알파벳이 들어가야 하므로 26가지 경우가 있을 수 있고, 만약 'd'라면 숫자가 들어가야 하므로 10가지 경우가 있을 수 있다. 여기서 추가로 문제에서 동일한 문자나 숫자가 두 번 연속해서 나올 수 없다고 했기 때문에 두 자리가 모두 'c'거나 모두 'd'라면 경우의 수를 한 가지 줄여서 계산해주어야 한다.

이렇게 해서 전체 총 경우에다가 계속 경우의 수를 곱해나가면 쉽게 해결할 수 있다.

3. 코드

전체 코드는 아래와 같다.

import java.util.*;
public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int ans = 1;
        for (int i=0; i<s.length(); i++) {
            int count = (s.charAt(i) == 'c' ? 26 : 10);
            if (i > 0 && s.charAt(i) == s.charAt(i-1)) {
                count --; //같은 문자열, 숫자 제외하기 위해서
            }
            ans = ans * count;
        }
        System.out.println(ans);
    }
}

알고리즘은 여러가지 방법으로 풀어보는 연습을 해야 실력도 늘고 생각하는 힘도 길러지는 것 같다. 한 가지 방법으로 풀어봤더라도 다양하게 연습해보자.