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)

BOJ_20207 달력 -Python3

문제분석

1. 관찰
- 우선 달력을 만들어준다.
- 일정이 겹치는 경우 행의 수를 +1
- 연속된 일정에서는 일정의 길이 +1로 카운트하며 행의 최대값을 구한다.
- 3의 값으로 직사각형의 크기를 구한다.

- 달력에서 row의 최대값과 col의 길이를 카운트 한 값을 곱해 박스값을 구한다.
!!주의. 끝이 0으로 끝나지 않는 경우가 있다. 이를 마지막에 더해주어야 한다.!!

2. 복잡도
- O(N*(E-S+1)+S) = 365*1000 ... >> 4만정도 가능

3. 자료구조
- 달력 int[]

해결코드

import sys 
si = sys.stdin.readline

N = int(si())
clndr = [0]*365

for _ in range(N):
    s, e = map(int, si().split())
    for i in range(s-1,e): # 겹치는 일정 높이 +1
        clndr[i] += 1

sum_area = 0
l, h = 0, 0

for i in clndr:
    h = max(h,i) 
    if i:
        l += 1
    else:
        sum_area += l*h
        l, h = 0, 0

sum_area += l*h # 끝이 0으로 끝나지 않는 경우

print(sum_area)