[백준] 10870번. 피노나치수 찾기(재귀) & 브루트포스 - 2798번. 블랙잭

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

 

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

 

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

 

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

 

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

 

 

 

입력

첫째 줄에 n이 주어진다. n은 20보다 작거나 같은 자연수 또는 0이다.

 

 

 

 

 

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

 

 

예제입력

해설 코드

n = int(input())

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

print(fib(n))

 

 

 

 

---

문제

브루트포스 - 2798번 블랙잭(백준)

브루트 포스 : Brute Force 로서, 모든 경우의 수를 탐색하면서 요구조건에 충족되는 결과만을 가져오는 문제이다

브루트포스 알고리즘의 특징은 모든 영역을 전체 탐색하는 방법이다.

전체 탐색하는 방법으로는 선형 구조를 전체적으로 탐색하는 순차 탐색,

비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS) 있다.

 

카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다.

 

한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다.

 

 

김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다.

 

 

이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.

 

 

N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.

 

 

 

 

입력

첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다.

 

합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.

 

 

 

 

 

출력

첫째 줄에 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력한다.

 

 

예제입력

해설 코드

첫번째 받는 수는 전체 카드의 개수이며,

 

다음으로 받는 수는 앞서 받은 수의 값의 리밋을 정해주는 값이며,

 

다음으로 전체 카드의 개수만큼 수를 입력해줘야한다 **

 

또한 앞서 나온 수들중에 3개를 조합하여 합이 가장 근접한 것들을

 

결과값으로 뽑아줘야 한다.

 

즉 3가지 정도의 일을 해야한다

 

n, m = map(int, input().split()) # 한줄에서 같이 받는 코드

card = list(map(int, input().split()))

res = set() # 집합으로 받으며, 중복을 허락하지 않는다


i = 0

while i < n-2: #0은 시작, n=3인 경우 3개를 뽑는 경우이므로, 전체 카드 수가 3장이므로 -> 1번만 가능하다 즉 i < n-2는 0만 가능하다(같거나 작지 않음)
    j = i + 1
    
    while j < n-1:
        k = j+1
        
        while k < n :
            if card[i] + card[j] + card[k] <= m:
                res.add(card[i] + card[j] + card[k])
            k += 1 # 끝단부터 하나씩 올리기, 지역변수로 이용
        j += 1 # 중간 자리수
    i += 1

print(n,m)
print(res)
print(max(res))

print()

 

#1. sorted()

정렬 메소드로서, 한번 사용하면 다시 돌리지 못한다, 집합을 목록인 리스트로 반환한다

이렇게 무작위 분포를 갖고 있는 집합에서

 

sorted로 덮어서 값을 출력하고, 다시 값을 출력하면

이미 값이 변했다

변한 값을 반영한 res 변수

 

목록을 리스트로 반환해서 뽑는 살짝 다른 방법