모각코 2회차

✏️ 코테 준비 백준 풀기

백트래킹

• N-Queen (🥉골드 4티어 )
• 연산자 끼워넣기 (🥈실버 1티어)
• 가르침 (🥉 골드 4티어)

이분탐색

• 랜선 자르기 (🥈실버 2티어 )

9663 N-Queen

---

def possible(x):
    for i in range(x):
        if chess[x]==chess[i] or abs(x-i)==abs(chess[x]-chess[i]):
            return False
    return True

def n_queens(i):
    global answer
    if i==n:
        answer+=1
        return
    else:
        for k in range(n):
            chess[i] = k
            if possible(i) ==1:
                n_queens(i+1)

n= int(input())
answer= 0
chess=[0]*n
n_queens(0)
print(answer)

---

14888 연산자 끼워넣기

---

import math
n = int(input())
num = list(map(int,input().split()))
cal = list(map(int,input().split()))

## cal[0] = '+'
## cal[1] = '-'
## cal[2] = '*'
## cal[3] = '/'
max_ans = -99999
min_ans = 99999
ans=0
def dfs(i,ans):
    global max_ans,min_ans,cal
    if i==n:
        max_ans  = max(max_ans,ans)
        min_ans = min(min_ans,ans)
    else:
        if cal[0]>0:
            cal[0] -=1
            dfs(i+1,ans+ num[i])
            cal[0] +=1
        if cal[1]>0:
            cal[1] -=1
            dfs(i+1,ans- num[i])
            cal[1] +=1
        if cal[2]>0:
            cal[2] -=1
            dfs(i+1,ans* num[i])
            cal[2] +=1
        if cal[3]>0:
            cal[3] -=1
            dfs(i+1,int(ans/ num[i]))
            cal[3] +=1

dfs(1,num[0])
print(max_ans)
print(min_ans)

---

1062 가르침

---

from collections import Counter
n, k = map(int,input().split())
if k<5:
    print(0)
    exit()
if k==26:
    print(n)
    exit()
words= []
for i in range(n):
    words.append(set(input()[4:-4]))


bit = [0]*26
d = ['a','n','t','c','i']
for i in d:
    bit[ord(i)-ord('a')]= 1

answer = 0
def dfs(idx,cnt):
    global answer
    if cnt == k-5:
        wc= 0
        for word in words:
            temp = True
            for j in word:
                if bit[ord(j)-ord('a')] == 0:
                    temp = False
                    break
            if temp == True:
                wc+=1
        answer= max(wc,answer)
        return

    for i in range(idx,26):
        if bit[i] ==0:
            bit[i] = 1
            dfs(i+1,cnt+1)
            bit[i] = 0

dfs(0,0)
print(answer)

---

1654 랜선 자르기

---

k,n = map(int,input().split())
line = []
for _ in range(k):
    line.append(int(input()))

left = 1
right = max(line)
mid_temp=[]
while(left<=right):
    mid = (left + right) // 2
    ans = 0
    for i in line:
        ans += i//mid
    if ans >=n:
        left = mid+1
    else:
        right = mid-1

print(right)

---