백준 온라인 저지, 자료구조 / 5568번: 카드놓기 (파이썬 / 백준 실버문제)

문제 주소: https://www.acmicpc.net/problem/5568

문제

상근이는 카드 n(4 ≤ n ≤ 10)장을 바닥에 나란히 놓고 놀고있다. 각 카드에는 1이상 99이하의 정수가 적혀져 있다. 상근이는 이 카드 중에서 k(2 ≤ k ≤ 4)장을 선택하고, 가로로 나란히 정수를 만들기로 했다. 상근이가 만들 수 있는 정수는 모두 몇 가지일까?

예를 들어, 카드가 5장 있고, 카드에 쓰여 있는 수가 1, 2, 3, 13, 21라고 하자. 여기서 3장을 선택해서 정수를 만들려고 한다. 2, 1, 13을 순서대로 나열하면 정수 2113을 만들 수 있다. 또, 21, 1, 3을 순서대로 나열하면 2113을 만들 수 있다. 이렇게 한 정수를 만드는 조합이 여러 가지 일 수 있다.

n장의 카드에 적힌 숫자가 주어졌을 때, 그 중에서 k개를 선택해서 만들 수 있는 정수의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이, 둘째 줄에 k가 주어진다. 셋째 줄부터 n개 줄에는 카드에 적혀있는 수가 주어진다.

출력

첫째 줄에 상근이가 만들 수 있는 정수의 개수를 출력한다.

제한

예제 입력 1

4
2
1
2
12
1

예제 출력 1

7

예제 입력 2

6
3
72
2
12
7
2
1

예제 출력 2

68

힌트

예제 1의 경우 상근이는 11, 12, 21, 112, 121, 122, 212를 만들 수 있다.

W3sicHJvYmxlbV9pZCI6IjU1NjgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNlNzRcdWI0ZGMgXHViMTkzXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjZTc0XHViNGRjIG4oNCAmbGU7IG4gJmxlOyAxMClcdWM3YTVcdWM3NDQgXHViYzE0XHViMmU1XHVjNWQwIFx1YjA5OFx1Yjc4MFx1ZDc4OCBcdWIxOTNcdWFjZTAgXHViMTgwXHVhY2UwXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVjZTc0XHViNGRjXHVjNWQwXHViMjk0IDFcdWM3NzRcdWMwYzEgOTlcdWM3NzRcdWQ1NThcdWM3NTggXHVjODE1XHVjMjE4XHVhYzAwIFx1YzgwMVx1ZDYwMFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3NzQgXHVjZTc0XHViNGRjIFx1YzkxMVx1YzVkMFx1YzExYyBrKDIgJmxlOyBrICZsZTsgNClcdWM3YTVcdWM3NDQgXHVjMTIwXHVkMGRkXHVkNTU4XHVhY2UwLCBcdWFjMDBcdWI4NWNcdWI4NWMgXHViMDk4XHViNzgwXHVkNzg4IFx1YzgxNVx1YzIxOFx1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjODE1XHVjMjE4XHViMjk0IFx1YmFhOFx1YjQ1MCBcdWJhODcgXHVhYzAwXHVjOWMwXHVjNzdjXHVhZTRjPzxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWNlNzRcdWI0ZGNcdWFjMDAgNVx1YzdhNSBcdWM3ODhcdWFjZTAsIFx1Y2U3NFx1YjRkY1x1YzVkMCBcdWM0ZjBcdWM1ZWMgXHVjNzg4XHViMjk0IFx1YzIxOFx1YWMwMCAxLCAyLCAzLCAxMywgMjFcdWI3N2NcdWFjZTAgXHVkNTU4XHVjNzkwLiBcdWM1ZWNcdWFlMzBcdWMxMWMgM1x1YzdhNVx1Yzc0NCBcdWMxMjBcdWQwZGRcdWQ1NzRcdWMxMWMgXHVjODE1XHVjMjE4XHViOTdjIFx1YjljY1x1YjRlNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIDIsIDEsIDEzXHVjNzQ0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWIwOThcdWM1ZjRcdWQ1NThcdWJhNzQgXHVjODE1XHVjMjE4IDIxMTNcdWM3NDQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjYxMCwgMjEsIDEsIDNcdWM3NDQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YjA5OFx1YzVmNFx1ZDU1OFx1YmE3NCAyMTEzXHVjNzQ0IFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI4MDdcdWFjOGMgXHVkNTVjIFx1YzgxNVx1YzIxOFx1Yjk3YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVjODcwXHVkNTY5XHVjNzc0IFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzAgXHVjNzdjIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPm5cdWM3YTVcdWM3NTggXHVjZTc0XHViNGRjXHVjNWQwIFx1YzgwMVx1ZDc4YyBcdWMyMmJcdWM3OTBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVhZGY4IFx1YzkxMVx1YzVkMFx1YzExYyBrXHVhYzFjXHViOTdjIFx1YzEyMFx1ZDBkZFx1ZDU3NFx1YzExYyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM4MTVcdWMyMThcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBuXHVjNzc0LCBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwIGtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWMxNGJcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIG5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2U3NFx1YjRkY1x1YzVkMCBcdWM4MDFcdWQ2MDBcdWM3ODhcdWIyOTQgXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM4MTVcdWMyMThcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVjNjA4XHVjODFjIDFcdWM3NTggXHVhY2JkXHVjNmIwIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCAxMSwgMTIsIDIxLCAxMTIsIDEyMSwgMTIyLCAyMTJcdWI5N2MgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI1NTY4IiwicHJvYmxlbV9sYW5nIjoiMiIsInRpdGxlIjoiXHUzMGFiXHUzMGZjXHUzMGM5XHU0ZTI2XHUzMDc5IiwiZGVzY3JpcHRpb24iOiI8cD5cdTgyYjFcdTViNTBcdTMwNTVcdTMwOTNcdTMwNmYgbiBcdTY3OWFcdWZmMDg0IFx1MjI2NiBuIFx1MjI2NiAxMFx1ZmYwOVx1MzA2ZVx1MzBhYlx1MzBmY1x1MzBjOVx1MzA5Mlx1NGUyNlx1MzA3OVx1MzA2Nlx1OTA0YVx1MzA5M1x1MzA2N1x1MzA0NFx1MzA4Ylx1ZmYwZSBcdTMwNWRcdTMwOGNcdTMwNWVcdTMwOGNcdTMwNmVcdTMwYWJcdTMwZmNcdTMwYzlcdTMwNmJcdTMwNmYgMSBcdTRlZTVcdTRlMGEgOTkgXHU0ZWU1XHU0ZTBiXHUzMDZlXHU2NTc0XHU2NTcwXHUzMDRjIDEgXHUzMDY0XHUzMDVhXHUzMDY0XHU2NmY4XHUzMDRiXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlIFx1ODJiMVx1NWI1MFx1MzA1NVx1MzA5M1x1MzA2Zlx1ZmYwY1x1MzA1M1x1MzA4Y1x1MzA4OVx1MzA2ZVx1MzBhYlx1MzBmY1x1MzBjOVx1MzA2ZVx1NGUyZFx1MzA0Ylx1MzA4OSBrIFx1Njc5YVx1ZmYwODIgXHUyMjY2IGsgXHUyMjY2IDRcdWZmMDlcdTMwOTJcdTkwNzhcdTMwNzNcdWZmMGMgXHU2YTJhXHU0ZTAwXHU1MjE3XHUzMDZiXHU0ZTI2XHUzMDc5XHUzMDY2XHU2NTc0XHU2NTcwXHUzMDkyXHU0ZjVjXHUzMDhiXHUzMDUzXHUzMDY4XHUzMDZiXHUzMDU3XHUzMDVmXHVmZjBlIFx1ODJiMVx1NWI1MFx1MzA1NVx1MzA5M1x1MzA2Zlx1NTE2OFx1OTBlOFx1MzA2N1x1NGY1NVx1N2EyZVx1OTg1ZVx1MzA2ZVx1NjU3NFx1NjU3MFx1MzA5Mlx1NGY1Y1x1MzA4Ylx1MzA1M1x1MzA2OFx1MzA0Y1x1MzA2N1x1MzA0ZFx1MzA4Ylx1MzA2MFx1MzA4ZFx1MzA0Nlx1MzA0Ylx1ZmYwZTxcL3A+XHJcblxyXG48cD5cdTRmOGJcdTMwNDhcdTMwNzBcdWZmMGMxLCAyLCAzLCAxMywgMjEgXHUzMDZlIDUgXHU2NzlhXHUzMDZlXHUzMGFiXHUzMGZjXHUzMGM5XHUzMDRjXHU0ZTBlXHUzMDQ4XHUzMDg5XHUzMDhjXHVmZjBjXHUzMDVkXHUzMDUzXHUzMDRiXHUzMDg5IDMgXHU2NzlhXHUzMDkyXHU5MDc4XHUzMDczXHU2NTc0XHU2NTcwXHUzMDkyXHU0ZjVjXHUzMDhiXHUzMDUzXHUzMDY4XHUzMDkyXHU4MDAzXHUzMDQ4XHUzMDhiXHVmZjBlIDIsIDEsIDEzIFx1MzA5Mlx1MzA1M1x1MzA2ZVx1OTgwNlx1MzA2Ylx1NGUyNlx1MzA3OVx1MzA4Ylx1MzA2OFx1ZmYwY1x1NjU3NFx1NjU3MCAyMTEzIFx1MzA5Mlx1NGY1Y1x1MzA4Ylx1MzA1M1x1MzA2OFx1MzA0Y1x1MzA2N1x1MzA0ZFx1MzA4Ylx1ZmYwZSBcdTMwN2VcdTMwNWZcdWZmMGMyMSwgMSwgMyBcdTMwOTJcdTMwNTNcdTMwNmVcdTk4MDZcdTMwNmJcdTRlMjZcdTMwNzlcdTMwNjZcdTMwODJcdWZmMGNcdTU0MGNcdTMwNThcdTY1NzRcdTY1NzAgMjExMyBcdTMwOTJcdTRmNWNcdTMwOGJcdTMwNTNcdTMwNjhcdTMwNGNcdTMwNjdcdTMwNGRcdTMwOGJcdWZmMGUgXHUzMDUzXHUzMDZlXHUzMDg4XHUzMDQ2XHUzMDZiXHVmZjBjXHU3NTcwXHUzMDZhXHUzMDhiXHUzMGFiXHUzMGZjXHUzMGM5XHUzMDZlXHU3ZDQ0XHUzMDdmXHU1NDA4XHUzMDhmXHUzMDViXHUzMDRiXHUzMDg5XHU1NDBjXHUzMDU4XHU2NTc0XHU2NTcwXHUzMDRjXHU0ZjVjXHUzMDg5XHUzMDhjXHUzMDhiXHUzMDUzXHUzMDY4XHUzMDgyXHUzMDQyXHUzMDhiXHVmZjBlPFwvcD5cclxuXHJcbjxwPm4gXHU2NzlhXHUzMDZlXHUzMGFiXHUzMGZjXHUzMGM5XHUzMDZiXHU2NmY4XHUzMDRiXHUzMDhjXHUzMDVmXHU2NTc0XHU2NTcwXHUzMDRjXHU0ZTBlXHUzMDQ4XHUzMDg5XHUzMDhjXHUzMDVmXHUzMDY4XHUzMDRkXHVmZjBjIFx1MzA1ZFx1MzA2ZVx1NGUyZFx1MzA0Ylx1MzA4OSBrIFx1Njc5YVx1MzA5Mlx1OTA3OFx1MzA3M1x1ZmYwY1x1NmEyYVx1NGUwMFx1NTIxN1x1MzA2Ylx1NGUyNlx1MzA3OVx1MzA4Ylx1MzA1M1x1MzA2OFx1MzA2N1x1NGY1Y1x1MzA4Ylx1MzA1M1x1MzA2OFx1MzA0Y1x1MzA2N1x1MzA0ZFx1MzA4Ylx1NjU3NFx1NjU3MFx1MzA2ZVx1NTAwYlx1NjU3MFx1MzA5Mlx1NmM0Mlx1MzA4MVx1MzA4Ylx1MzBkN1x1MzBlZFx1MzBiMFx1MzBlOVx1MzBlMFx1MzA5Mlx1NGY1Y1x1NjIxMFx1MzA1Ylx1MzA4OFx1ZmYwZTxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHU1MTY1XHU1MjliXHUzMDZmIDIrbiBcdTg4NGNcdTMwNGJcdTMwODlcdTMwNmFcdTMwOGJcdWZmMGUgMSBcdTg4NGNcdTc2ZWVcdTMwNmJcdTMwNmZcdTMwYWJcdTMwZmNcdTMwYzlcdTMwNmVcdTY3OWFcdTY1NzAgbiBcdWZmMDg0IFx1MjI2NiBuIFx1MjI2NiAxMFx1ZmYwOVx1MzA0Y1x1ZmYwYyAyIFx1ODg0Y1x1NzZlZVx1MzA2Ylx1MzA2Zlx1MzBhYlx1MzBmY1x1MzBjOVx1MzA5Mlx1OTA3OFx1MzA3Nlx1Njc5YVx1NjU3MCBrIFx1ZmYwODIgXHUyMjY2IGsgXHUyMjY2IDRcdWZmMDlcdTMwNGNcdTY2ZjhcdTMwNGJcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGUgMitpIFx1ODg0Y1x1NzZlZVx1ZmYwODEgXHUyMjY2IGkgXHUyMjY2IG5cdWZmMDlcdTMwNmJcdTMwNmYgaSBcdTY3OWFcdTc2ZWVcdTMwNmVcdTMwYWJcdTMwZmNcdTMwYzlcdTMwNmJcdTY2ZjhcdTMwNGJcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGIgMSBcdTRlZTVcdTRlMGEgOTkgXHU0ZWU1XHU0ZTBiXHUzMDZlXHU2NTc0XHU2NTcwXHUzMDRjXHU2NmY4XHUzMDRiXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHU1MWZhXHU1MjliXHUzMDZmXHVmZjBjXHU4MmIxXHU1YjUwXHUzMDU1XHUzMDkzXHUzMDRjXHU0ZjVjXHUzMDhiXHUzMDUzXHUzMDY4XHUzMDRjXHUzMDY3XHUzMDRkXHUzMDhiXHU2NTc0XHU2NTcwXHUzMDZlXHU1MDBiXHU2NTcwXHUzMDZlXHUzMDdmXHUzMDkyXHU1NDJiXHUzMDgwIDEgXHU4ODRjXHUzMDRiXHUzMDg5XHUzMDZhXHUzMDhiXHVmZjBlPFwvcD5cclxuIiwiaGludCI6IjxwPlx1NTE2NVx1NTI5Ylx1NGY4YiAxIFx1MzA2Ylx1MzA0YVx1MzA0NFx1MzA2Nlx1ZmYwYyAxLCAyLCAxMiwgMSBcdTMwNmUgNCBcdTY3OWFcdTMwNmVcdTMwYWJcdTMwZmNcdTMwYzlcdTMwNmVcdTRlMmRcdTMwNGJcdTMwODkgMiBcdTY3OWFcdTMwOTJcdTkwNzhcdTMwNzNcdWZmMGNcdTZhMmFcdTRlMDBcdTUyMTdcdTMwNmJcdTRlMjZcdTMwNzlcdTMwNjZcdTRmNWNcdTMwOGJcdTMwNTNcdTMwNjhcdTMwNGNcdTMwNjdcdTMwNGRcdTMwOGJcdTY1NzRcdTY1NzBcdTMwNmZcdWZmMGMgMTEsIDEyLCAyMSwgMTEyLCAxMjEsIDEyMiwgMjEyIFx1MzA2ZSA3IFx1NTAwYlx1MzA2N1x1MzA0Mlx1MzA4Ylx1ZmYwZTxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiSmFwYW5lc2UifV0=

접근 방법

- k개 만큼 수를 뽑아 정수를 만들어 이를 set에 넣고 모든 정수만들기가 끝났을 때 set의 길이를 출력한다.

코드

# https://www.acmicpc.net/problem/5568
# 접근 방법
# k개 만큼 수를 뽑아 정수를 만들어 이를 set에 넣고 모든 정수만들기가 끝났을 때 set의 길이를 출력한다.
def create_int(integer, count, checkList):
    if count > k:
        Integer.add(int(integer))
        return
    for i in range(n):
        if i not in checkList:
            create_int(integer + cards[i], count+1, checkList + [i])

n = int(input())
k = int(input())
cards = [input() for _ in range(n)]
Integer = set([])
create_int('', 1, [])
print(len(Integer))