BOJ_15649 N과 M (1) - Python3

문제 접근

1. 아이디어
- 백트래킹 재귀함수 안에서 for loop를 돌면서 숫자 선택 & 방문여부 확인
- 재귀함수에서 M개를 선택할 경우 print

2. 복잡도
- N! > 가능(8까지 가능)

3. 자료구조
- 결과값 저장 int[]
- 방문여부 체크 bool[]

해결 코드 1

import sys
input = sys.stdin.readline

N,M = map(int, input().split())
result = []
check = [False]*(N+1)

def recur(num):
    if num == M:
        print(' '.join(map(str, result)))
        return
    for i in range(1, N+1):
        if check[i] == False:
            check[i] = True # 방문
            result.append(i)
            recur(num+1)
            check[i] = False
            result.pop()

recur(0)

해결 코드 2

import sys
si = sys.stdin.readline

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

s = []
def f():
    if len(s) == M:
        print(' '.join(map(str,s)))
        return

    for i in range(1,N+1):
        if i in s:
            continue
        s.append(i)
        f()
        s.pop()
f()

같은 풀이이지만 방문여부를 코드 2 처럼 판별하면 코드가 간결해진다.

BOJ_15686 치킨 배달 - Python3

문제 분석

1. 관찰
- 전체 치킨 집에서 중복없이 M 개의 치킨집을 선택하여 탐색
- combinations를 통해 m개 선택한 경우에 대하여 최소값의 합을 구한다.

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

3. 자료구조
- 집, 치킨집: int[]
- 거리합 : int

해결 코드

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

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

h = [] # 집의 위치
c = [] # 치킨집의 위치

for i in range(N):
    tmp = list(map(int, si().split()))
    for j in range(N):
        if tmp[j] == 1:
            h.append([i,j])
        if tmp[j] == 2:
            c.append([i,j])


ans = float("inf")

for chicken in combinations(c, M):
    sum = 0
    for hou in h:
        sum += min([abs(hou[0]-chi[0])+abs(hou[1]-chi[1]) for chi in chicken])
    if ans>sum:
        ans = min(ans, sum)
print(ans)

BOJ_16918 봄버맨

문제 분석

1. 관찰
- 첫 번째 폭탄이 터진 형태와 두 번째 폭탄이 터진 형태가 3번째 부터 반복된다.
- 첫 폭탄 폭파 3,7,11...
- 둘째 폭탄 폭파 5,9,14...
... 코드 참고

2. 복잡도
- O(R*C) = 200*200*8 >> 가능

3. 자료 구조
- 폭탄 배열: int[][]

해결 코드

import sys
si = sys.stdin.readline

R, C, N = map(int, si().split())
board = [list(si().strip()) for _ in range(R)]


if N<=1: # 첫 1초동안은 인풋을 출력
    for li in board: print(''.join(li))
elif N%2 == 0: # 짝수번째는 폭탄이 모두 차 있는 형태
    for i in range(R): print('O'*C)
else: # 첫 폭탄이 터진 이후 3번째 부터 형태가 반복된다. 3,7,11 ... 과 5,9,13...

    bom_1 = [["O"]*C for _ in range(R)] # 첫 폭탄 터짐
    for i in range(R):
        for j in range(C):
            if board[i][j] == "O":
                for y, x in [(0, 0),(0, 1), (0, -1), (1, 0), (-1, 0)]:
                    ny, nx = y+i, x+j
                    if 0 <= ny < R and 0 <= nx < C:
                        bom_1[ny][nx] = '.'

    bom_2 = [["O"]*C for _ in range(R)] # 두 번째 폭탄 터짐
    for i in range(R):
        for j in range(C):
            if bom_1[i][j] == "O":
                for y, x in [(0, 0),(0, 1), (0, -1), (1, 0), (-1, 0)]:
                    ny, nx = y+i, x+j
                    if 0 <= ny < R and 0 <= nx < C:
                        bom_2[ny][nx] = '.'

    if N%4==3:
        for li in bom_1: print(''.join(li))
    if N%4==1:
        for li in bom_2: print(''.join(li))

BOJ_20115 에너지 드링크

문제 분석

1. 관찰
- 최대로 만들 수 있는 에너지 드링크의 양은
- 직관적으로 가장 큰 값을 a로 선택하고 나머지 음료들의 절반을 다 더한 값과 같음을 알 수 있다.

2. 복잡도
- max() = O(N)
- sum() = O(N)
>> 100000 + 100000 >> 가능

3. 자료구조
- int

해결 코드

import sys
si = sys.stdin.readline

N = int(si())
drinks = list(map(int, si().split()))

M = max(drinks)
S = sum(drinks)

print(M+(S-M)/2)

BOJ_21314 민겸 수

문제 분석

1. 관찰
- 연속된 M은 M의 개수(cnt) -1이 자리수이다 -> 1E(cnt-1)
- K가 있는 경우 -> 5E(cnt)
- K에서 끊어준다.

- M 묶음으로 끊어주면 최소값이 된다.
- M과 K를 묶음으로 해준 경우 최대값이 된다.
... 코드 참고


2. 복잡도
- O(N) = S의 길이 >> 가능

3. 자료구조
- 최대, 최소 : 문자열

해결 코드

import sys
si = sys.stdin.readline

S = si().strip()
MAX = "" 
MIN = ""
cnt_m = 0  # 연속된 m의 개수 count

for i in range(len(S)):
    if S[i] == 'M':
        cnt_m +=1
    elif S[i] == 'K':
        if cnt_m: # M이 연속된 경우
            MAX += str(5*(10**cnt_m)) # M, K 함께 5의 배수로
            MIN += str(10**cnt_m+5) # M은 1의 배수로, K는 5로 더해서 추가
        else: # K만 단독으로 있는 경우, K는 단독으로 있기 때문에 5로만 끊어서 추가한다.
            MAX += "5"
            MIN += "5"
        cnt_m = 0

if cnt_m: # 끝이 M으로 끝나는 경우
    MIN += str(10**(cnt_m-1))
    while cnt_m: # 최대값을 만들기 위해서는 M의 연속의 경우 1111로 만들어 주어야 함으로 loop
        MAX += "1"
        cnt_m -= 1

print(MAX)
print(MIN)

BOJ_2667 단지번호붙이기 - Python3

문제 접근

1. 아이디어
- dfs로 단지 방문
- 방문하며 단지 번호 붙이기
- dfs에서 가구수 카운팅

2. 복잡도
- O(V+E) : 5*25*25 >> 가능

3. 자료구조
- 지도: int[][]
- 방문기록: bool[][]

해결 코드

import sys
input = sys.stdin.readline

N = int(input())

map = [input().strip() for _ in range(N)]
visited = [[0]*N for _ in range(N)]

dx =[-1,1,0,0]
dy =[0,0,-1,1]

groupCnt = 0
houseCnt =[]

def dfs(y,x):
    visited[y][x] = 1
    houseCnt[groupCnt]+=1
    for i in range(4):
        ny,nx = y + dy[i], x + dx[i]
        if 0<= ny < N and 0<= nx < N:
            if map[ny][nx] == '1' and visited[ny][nx] == 0:
                dfs(ny,nx)

for j in range(N):
    for i in range(N):
        if map[j][i] == '1' and visited[j][i] == 0:
            houseCnt.append(0)
            dfs(j,i)
            groupCnt +=1

print(groupCnt)
houseCnt.sort()
for e in houseCnt:
    print(e)