BOJ_2309 일곱 난쟁이 -Python3

문제분석

1. 관찰
- 아홉 난쟁이의 키가 중어진다.

!! 잘못 생각 한 풀이 => 난쟁이의 키가 같은 경우를 생각하지 않고 재귀함수로 조합을 구현하려고 했다.
- 9 중 7을 뽑는 모든 경우를 탐색한다. -> 재귀함수로 구현
- 7명의 키 합이 100이 되는 경우 출력한다. -> 7명이 선택된 경우, 합이 100이면 출력

!! 해결 풀이
- 9명중 2을 제거한 모든 경우를 탐색한다.
- 

2. 복잡도
- O(9P2) = (9!)/(2!*8!) >> 가능

3. 자료구조
- 난쟁이 : int[]

해결코드

import sys
si = sys.stdin.readline

dwarves = []
for _ in range(9):
    dwarves.append(int(si()))

dwarves.sort() # 오름차순 정렬

S = sum(dwarves)
sum = 0
for i in range(9):
    for j in range(i+1,9):
        sum = S-dwarves[i]-dwarves[j]
        if sum == 100:
            for d in dwarves:
                if d == dwarves[i]:
                    continue
                if d == dwarves[j]:
                    continue
                else:
                    print(d)
            break
    if sum == 100:
        break

BOJ_7568 덩치 -Python3

문제분석

1. 관찰
- 키와 몸무게가 모두 큰 경우 덩치를 크다고 판단한다.
- 조건에 해당 될때 +1을 해준다. 

2. 복잡도
- O(N+N**N+N) = 50 +50**50+50 >> 가능

3. 자료구조
- 신체조건 : list[]
- 몸무게가 큰 사람의 수: dict{int:int}

해결코드

from collections import defaultdict
import sys
si = sys.stdin.readline

N = int(si())
p = []
p_dict = defaultdict(int)

for i in range(N):
    p.append(list(map(int,si().split())))
    p_dict[i] =1
for i in range(N):
    for j in range(N):
        if p[i][0] < p[j][0] and p[i][1] < p[j][1]:
            p_dict[i] +=1
for i in p_dict.values():
    print(i, end=" ")

BOJ_1436 영화감독 숌 -Python3

문제분석

1. 관찰
- 666이 들어간 수를 카운팅
- cnt == N 영화 수 출력 

2. 복잡도
- O(n) 
- N이 10000일때 ans가 266799 임으로 >> 가능

3. 자료구조
- 영화번호, 번째 카운팅: int

해결코드

import sys 
si = sys.stdin.readline

N = int(si())

cnt = 0
ans = 666
while True:
    if "666" in str(ans):
        cnt+=1
    if cnt == N: # N번째 제목에 들어간 수 출력후 loop 종료
        print(ans)
        break
    ans+=1

BOJ_2231 분해합 -Python3

문제분석

1. 관찰
- 분해합: N을 이루는 각 자리수의 합
- m을 증가시켜가며 sum 을 N과 비교한다.
- N과 같을 때 출력하고
- N과 같은 경우가 없는 경우 for - else 구문으로 0을 출력한다.

2. 복잡도
- O(N) = 1,000,000 >> 가능

3. 자료구조
- 각자리수 분해 : int[] -> list(map(int, str(i)))

해결코드

import sys
si = sys.stdin.readline

N = int(si())
for i in range(1,N):
    s = i + sum(list(map(int,str(i))))
    if s == N:
        print(i)
        break 
else: # 생성자가 없는 경우 0 출력, for - else 구문
    print(0)

순열(permutations)

서로 다른 n개의 원소에서 r개를 중복없이 골라 순서대로 나열하는 경우의 수

순열 구현

def permutation(arr,r):
    arr = sorted(arr)
    used = [0 for _ in range(len(arr))]

    def generate(chosen, used):
        if len(chosen) == r:
            print(chosen)
            return

        for i in range(len(arr)):
            if not used[i]:
                chosen.append(arr[i])
                used[i] = 1
                generate(chosen, used)
                used[i] = 0
                chosen.pop()

    generate([],used)

조합(Combinations)

서로 다른 n개의 원소에서 r개를 뽑는 경우의 수

조합 구현

def combination(arr, r):
    arr = sorted(arr)
    used = [0 for _ in range(len(arr))]

    def generate(chosen):
        if len(chosen) == r:
            print(chosen)
            return

        start = arr.index(chosen[-1]) + 1 if chosen else 0
        for nxt in range(start, len(arr)):
            if used[nxt] == 0 and (nxt == 0 or arr[nxt-1] != arr[nxt] or used[nxt-1]):
                chosen.append(arr[nxt])
                used[nxt] = 1
                generate(chosen)
                chosen.pop()
                used[nxt] = 0
    generate([])

순열, 조합 파이썬 라이브러리

itertools

import itertools
pool = ['A','B','C']
print(list(map("".join, itertools.permutaions(pool, 2)))) # 순열
print(list(map("".join, itertools.combinations(pool, 2)))) # 조합

참고

• https://velog.io/@yeseolee/python%EC%9C%BC%EB%A1%9C-%EC%88%9C%EC%97%B4%EA%B3%BC-%EC%A1%B0%ED%95%A9-%EC%A7%81%EC%A0%91-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0

BOJ_2798 블랙잭 -Python3

문제분석

1. 관찰
- N장의 카드 중에서 3장의 카드를 골라 M과 최대한 가까운 수를 만든다.
- 주어진 카드에서 3장을 뽑을 수 있는 모든 조합을 탐색한다.

2. 복잡도
- O(nC3) = 100! / (3!*97!) = (100*99*98)/(3*2*1) >> 가능

3. 자료구조
- 카드 = int[]

해결코드 1

from itertools import combinations
import sys
si = sys.stdin.readline

N, M = map(int, si().split())
cards = list(map(int, si().split()))


picked = []

ans = 0

for picked in combinations(cards, 3):
    sum_pick = sum(picked)
    if sum_pick <= M:
        ans = max(ans, sum_pick)

print(ans)

해결코드 2

import sys
si = sys.stdin.readline

N, M = map(int, si().split())
cards = list(map(int, si().split()))
ans = 0

for i in range(N):
    for j in range(i+1, N):
        for k in range(j+1, N):
            sum_c = cards[i]+cards[j]+cards[k]
            if sum_c <=M:
                ans = max(ans,sum_c)

print(ans)