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)

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)

BOJ_1065 한수 -Python3

문제분석

1. 관찰
- 한수: x의 각 자리가 등차수열을 이루는 수
- 범위가 1000 미만의 수에 한정되어있으므로 세자리 수 까지 고려한다.
- 2자리 수 까지는 모두 한수
- 3자리 수는 값의 차이를 직접 비교하여 맞는 경우만 카운트한다.

2. 복잡도
- O(N) = 999 >> 가능

3. 자료구조
- 한수: int

해결코드

import sys
si = sys.stdin.readline

N = int(si())

num = 0
ans = 0
while num < N:
    num += 1
    if num < 100: # 2자리수 까지는 모두 한수
        ans+=1
    if 100 <= num: # 3자리 한수는 차이를 비교
        a,b,c = num//100, (num%100)//10, num%10

        if a-b == b-c:
            ans+=1

print(ans)