모각코 3회차

✏️ 코테 준비 백준 풀기

Back Tracking

• N과 M(2) (🥈실버 3티어 )
  
  

DP

• 구간 합 구하기(5) (🥈실버 1티어 )
  
  

Data Structure

• 카드 정렬하기 (골드 4티어 )
• 괄호의 값 (🥈실버 1티어 )
  
  

Graph

• 토마토 (골드 5티어)

15650 N과 M(2)

---

n,m = map(int,input().split())

s= []
def func(start):
    if len(s)==m:
        print(' '.join(map(str,s)))
        return
    for i in range(start,n+1):
        if i not in s:
            s.append(i)
            func(i+1)
            s.pop()

func(1)

---

11660 구간 합 구하기(5)

---

import heapq
n = int(input())
d=[]
for _ in range(n):
    heapq.heappush(d,int(input()))
if n==1:
    print(0)
    exit()
ans = 0
while(len(d)>1):
    temp = heapq.heappop(d) + heapq.heappop(d)
    ans+=temp
    heapq.heappush(d,temp)
print(ans)

---

1715 카드 정렬하기

---

import heapq
n = int(input())
d=[]
for _ in range(n):
    heapq.heappush(d,int(input()))
if n==1:
    print(0)
    exit()
ans = 0
while(len(d)>1):
    temp = heapq.heappop(d) + heapq.heappop(d)
    ans+=temp
    heapq.heappush(d,temp)
print(ans)

---

2504 괄호의 값

---

s = input()
stack = []
answer=0
tmp = 1
for i in range(len(s)):
    if s[i]=="(":
        stack.append(s[i])
        tmp*=2

    elif s[i]=="[":
        stack.append(s[i])
        tmp*=3

    elif s[i]==")":
        if not stack or stack[-1]=="[":
            answer = 0
            break
        if s[i-1]=="(":
            answer +=tmp
        tmp//=2
        stack.pop()

    elif s[i]=="]":
        if not stack or stack[-1]=="(":
            answer = 0
            break
        if s[i-1]=="[":
            answer +=tmp
        tmp//=3
        stack.pop()

    # print(s[i],"ans :",answer,"tmp :",tmp)
if stack:
    answer=0
print(answer)

---

7576 토마토

---

import copy
from collections import deque

def bfs(cnt):

    dx= [0,0,1,-1]
    dy= [1,-1,0,0]
    while(q):
        cnt,x,y = q.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if (0<=nx<m and 0<=ny<n) and graph[nx][ny] ==0:
                graph[nx][ny] = 1
                q.append((cnt+1,nx,ny))
    return cnt


n,m = map(int,input().split())
graph = []
for i in range(m):
    graph.append(list(map(int,input().split())))

q = deque()
for i in range(m):
    for j in range(n):
        if graph[i][j]==1:
            q.append((0,i,j))


ans = bfs(0)
cnt= 0
for i in graph:
    cnt += i.count(0)

print(-1 if cnt else ans)

---