[BOJ]완전탐색&이진탐색 44제
Coding Test Study 2
💻221118~221130 (브3~브1)
1. 약수 구하기 (브3) 2501
N, K = map(int, input().split())
cnt = 0
f = 0
for i in range (1, N+1):
if N%i == 0 :
cnt += 1
if cnt == K:
f = 1
break
if f == 0 :
print(0)
else :
print(i)
2. 분해합 (브2) 2231
import sys
input = sys.stdin.readline
N = int(input())
n = 0
f = 0
while True :
if N == n + sum(map(int, str(n))):
print(n)
break
if n > N:
print(0)
break
n += 1
3. 블랙잭 (브2) 2798
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
card = list(map(int, input().split()))
result = 0
for i in range (N) :
for j in range (i+1, N):
for k in range (j+1, N):
if card[i]+card[j]+card[k] > result and card[i]+card[j]+card[k] <= M : #카드 세개의 합이 최댓값이면서 M보단 작을 때
result = card[i]+card[j]+card[k]
print(result)
4. 일곱 난쟁이 (브1) 2309
import sys
input = sys.stdin.readline
height = [int(input()) for _ in range(9)]
s = sum(height)
f = 0
for i in range (9):
for j in range (i+1, 9):
if s-height[i]-height[j] == 100:
height.pop(j)
height.pop(i)
f = 1
break
if f == 1 :
break
height.sort()
for i in range (7):
print(height[i])
5. 유레카 이론 (브1) 10448
import sys
input = sys.stdin.readline
def isEureka(n):
for i in range (1, n):
for j in range (i, n-i):
k = n-i-j
if i in Tri and j in Tri and k in Tri:
return 1
return 0
#삼각수 배열
Tri = [i*(i+1)/2 for i in range(1, 46)]
#입력
T = int(input())
for i in range (T):
print(isEureka(int(input())))
💻221201~221207 (실5~실4)
6. 영화감독 숌 (실5) 1436
import sys
input = sys.stdin.readline
N = int(input())
cnt = 0
n = 665
while True :
while True :
n += 1
if '666' in str(n) :
cnt += 1
result = n
break
if cnt == N :
break
print(result)
7. 숫자 카드 (실5) 10815
import sys
input = sys.stdin.readline
#이진 탐색 함수
def binary_search(array, target, start, end):
if start > end :
return None
mid = (start + end)//2
if array[mid] == target:
return mid
elif array[mid] > target :
return binary_search(array, target, start, mid-1)
else :
return binary_search(array, target, mid+1, end)
N = int(input())
card1 = list(map(int, input().split()))
M = int(input())
card2 = list(map(int, input().split()))
result = ''
card1.sort()
for i in range(M):
bs = binary_search(card1, card2[i], 0, N-1)
if bs == None :
result += '0 '
else :
result += '1 '
print(result)
8. 덩치 (실5) 7568
import sys
input = sys.stdin.readline
N = int(input())
person = [list(map(int, input().split())) for _ in range(N)]
result = []
for i in range (N):
cnt = 1
for j in range (N):
if person[j][0]>person[i][0] and person[j][1]>person[i][1]:
cnt += 1 #본인보다 키도 크고 몸무게도 큰 사람 수 세기
print(cnt, end=" ")
9. 암기왕 (실4) 2776
import sys
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
T = int(input())
for i in range (T):
#입력
N = int(input())
note1 = list(map(int, input().split()))
M = int(input())
note2 = list(map(int, input().split()))
#이진탐색은 정렬 필수
note1.sort()
for j in range (M):
if bisect_right(note1, note2[j])-bisect_left(note1, note2[j])>0:
print(1)
else :
print(0)
10. 체스판 다시 칠하기 (실4) 1018
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
board = []
for i in range (N):
board.append(list(input().rstrip()))
# 첫 값이 1.B일 때와 2.W일 때 둘다 계산해서 둘 중에 작은 수로 갱신한다
# 두 가지 경우를 나눠서 세는 것이 아닌 다른 변수로 카운트 해서 한번에 계산한다
result = N*M
for i in range (N-7):
for j in range (M-7):
cnt_b = 0 #1. 첫 값이 B일 때 개수(홀수 : B, 짝수 : W)
cnt_w = 0 #2. 첫 값이 W일 때 개수(홀수 : W, 짝수 : B)
for k in range(8):
for l in range(8):
if (i+j+k+l)%2 == (i+j)%2:
if board[i+k][j+l] == 'B': #홀수 번째가 B일 때 첫 값이 W라면 바뀌어야함
cnt_w += 1
else: #홀수 번째가 W일 때 첫 값이 B라면 바뀌어야함
cnt_b += 1
if (i+j+k+l)%2 != (i+j)%2: #짝수 번째도 똑같이 카운트 해줌
if board[i+k][j+l] == 'W':
cnt_w += 1
else:
cnt_b += 1
if min(cnt_b, cnt_w) < result: #둘 중 작은 값으로 갱신
result = min(cnt_b, cnt_w)
print(result)
💻221208~221214 (실4~실3)
11. 문자열 (실4) 1120
A, B = input().split()
# 알파벳 추가는 상관하지 않는다
result = len(A)
for i in range (len(B)-len(A)+1):
cnt = 0
for j in range (len(A)):
if A[j] != B[i+j]:
cnt += 1
if cnt < result : #다른 문자가 제일 적을 때
result = cnt
print(result)
12. 수찾기 (실4) 1920
import sys
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
M = int(input())
B = list(map(int, input().split()))
A.sort()
for i in range (M):
if bisect_right(A, B[i])-bisect_left(A, B[i])>0:
print(1)
else :
print(0)
13. 숫자 카드2 (실4) 10816
import sys
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
N = int(input())
card1 = list(map(int, input().split()))
M = int(input())
card2 = list(map(int, input().split()))
card1.sort()
for i in range(M):
result = bisect_right(card1, card2[i])-bisect_left(card1, card2[i])
print(result, end=' ')
14. 한수 (실4) 1065
import sys
input = sys.stdin.readline
N = int(input())
cnt = 0
for i in range (1, min(N+1, 1000)):
if i < 100 :
cnt += 1
else :
if (i%10 + i//100)/2 == (i%100)//10: #(일의 자리수+백의 자리수)/2 == 십의 자리수
cnt += 1
print(cnt)
15. 사탕 게임 (실3) 3085
import sys
input = sys.stdin.readline
N = int(input())
C = [list(input().rstrip()) for _ in range(N)]
def max_color(array): # 연속된 색의 최댓값 세주는 함수
result = 0
for i in range(len(array[0])):
# 가로 확인
a = array[i] #가로 배열
init = a[0]
max_a = 0
cnt = 1
for j in range(1, len(array[0])):
if a[j] == init :
cnt += 1
else :
init = a[j]
cnt = 1
if cnt > max_a :
max_a = cnt
# 세로 확인
b = [c[i] for c in array] #세로 배열
init = b[0]
max_b = 0
cnt = 1
for j in range(1, len(array[0])):
if b[j] == init :
cnt += 1
else :
init = b[j]
cnt = 1
if cnt > max_b :
max_b = cnt
#가로, 세로 중 더 큰 값을 result에 갱신
if max(max_a, max_b) > result:
result = max(max_a, max_b)
return result
r = [] #max_color의 반환값을 모두 넣는 배열
for i in range (N):
for j in range (N):
if i != N-1 :
C[i][j], C[i+1][j] = C[i+1][j], C[i][j] #위치 바꾸고
r.append(max_color(C)) #함수 통해서 확인 후
C[i][j], C[i+1][j] = C[i+1][j], C[i][j] #다시 원래 위치로 바꿈
if j != N-1 :
C[i][j], C[i][j+1] = C[i][j+1], C[i][j]
r.append(max_color(C))
C[i][j], C[i][j+1] = C[i][j+1], C[i][j]
#최댓값 갱신 하는 것이 아닌 모든 값을 배열에 넣은 후 거기서 최댓값 출력
print(max(r))
💻221215~221221 (실3~실2)
16. 숫자 야구 (실3) 2503
import sys
input = sys.stdin.readline
N = int(input())
num = []
for i in range (N):
num.append(list(map(int, input().split())))
num[i][0] = list(map(int,str(num[i][0])))
result = 0
for i in range (111, 1000):
i = list(map(int,str(i)))
#숫자에 0이 포함되어 있으면 제외
if 0 in i :
continue
#서로 다른 세 숫자일 때
if i[0] != i[1] and i[1] != i[2] and i[2] != i[0] :
cnt = 0
for j in range (N):
strike = 0
ball = 0
for k in range(3):
if i[k] == num[j][0][k] :
strike += 1
if i[k] in num[j][0] and i[k] != num[j][0][k] :
ball += 1
#strike와 ball 결과값이 같을 때 cnt+1
if strike == num[j][1] and ball == num[j][2]:
cnt += 1
#strike와 ball 결과값이 전부 다 같을 때 result+1
if cnt == N :
result += 1
print(result)
17. 예산 (실3) 2512
import sys
input = sys.stdin.readline
N = int(input())
X = list(map(int, input().split()))
budget = int(input())
start = 0
end = max(X)
result = 0
while (start <= end) :
total = 0
mid = (start+end)//2
for x in X:
if x > mid : #mid값보다 크다면 mid값을 더해주고
total += mid
else : #mid값보다 작다면 원래값 더해줌
total += x
if total <= budget: #예산보다 작거나 같으면
result = mid #result값 갱신해주고
start = mid+1 #mid값을 늘려나감
else:
end = mid-1 #예산보다 크면 mid 줄여나감
print(result)
18. IF문 좀 대신 써줘 (실3) 19637
import sys
input = sys.stdin.readline
#입력(칭호와 전투력을 다른 배열에 넣는게 편함)
N, M = map(int, input().split())
name = []
value = []
for i in range (N):
n, v = map(str, input().split())
name.append(n)
value.append(int(v))
#이진탐색
for i in range (M):
power = int(input())
start = 0
end = N-1
while (start <= end):
mid = (start+end)//2
if power <= value[mid]: #입력값이 중간 전투력보다 작거나 같을 때
result = name[mid]
end = mid-1
else :
start = mid+1
print(result)
19.게임 (실3) 1072
import sys
input = sys.stdin.readline
X, Y = map(int, input().split())
win = Y
Z = int(Y*100/X)
if X == Y or Z >= 99:
print(-1)
#파라매트릭 서치
else :
start = Y
end = X*2 #X로 할 때는 틀렸고 X*2로 할 때는 맞음(이분 탐색시 충분히 큰 값을 써도 괜찮음)
while start <= end:
mid = (start+end)//2
X = (mid)-Y+X
Y = mid
if Z < int(Y*100/X):
result = mid
end = mid-1
else:
start = mid+1
print(result-win)
20.부분수열의 합 (실2) 1182
# 백트래킹으로 풀면 됨
# 부분 수열은 선택하거나 안 하거나
import sys
input = sys.stdin.readline
N, S = map(int, input().split())
array = list(map(int, input().split()))
cnt = 0
def bt(idx, total):
global cnt
if idx == N :
if total == S :
cnt += 1
return
bt(idx+1, total) #선택 안 하거나
bt(idx+1, total+array[idx]) #선택하거나
bt(0, 0)
if S == 0:
cnt -=1
print(cnt)
💻221222~230111 (실2~실2)
21.꽃길 (실2) 14620
import sys
input = sys.stdin.readline
N = int(input())
G = [list(map(int, input().split())) for _ in range(N)]
# f는 0으로 초기화된 배열, 방문했다면 1로 바꿔준다
def isVisited(r, c):
f[r-1][c], f[r+1][c], f[r][c-1], f[r][c+1], f[r][c] = 1, 1, 1, 1, 1
total = G[r-1][c] + G[r+1][c] + G[r][c-1] + G[r][c+1] + G[r][c]
return total
n = (N-2)*(N-2)
r = []
# i, j, k를 일차원 배열에 있다고 생각하고 돌린다
# i, j, k는 전체 배열 G의 테두리에 있는 것을 뺀 배열이다 (N-2 * N-2)
# i, j, k로 G에서의 위치를 구할 수 있다 (i = 0일 때 i는 G[1][1]에 위치함)
for i in range (0, n-2):
for j in range (i+1, n-1):
for k in range (j+1, n):
f = [[0]*N for _ in range(N)]
result = 0
result += isVisited(i//(N-2)+1, i%(N-2)+1)
result += isVisited(j//(N-2)+1, j%(N-2)+1)
result += isVisited(k//(N-2)+1, k%(N-2)+1)
cnt = 0
for l in range (N):
cnt += f[l].count(1)
if cnt == 15: # 서로 다 겹치지 않을 때
r.append(result) # 최솟값 갱신이 아닌 배열에 넣는다
print(min(r))
22.스타트와 링크 (실2) 14889
import sys
from itertools import combinations
input = sys.stdin.readline
N = int(input())
T = [list(map(int, input().split())) for _ in range(N)]
idx = [i for i in range(N)]
result = sys.maxsize
for s in list(combinations(idx, N//2)) :
start = 0
link = 0
l = list(set(idx) - set(s))
for i, j in list(combinations(s, 2)) :
start += T[i][j] + T[j][i]
for i, j in list(combinations(l, 2)) :
link += T[i][j] + T[j][i]
result = min(result, abs(start-link))
print(result)
23.용돈 관리 (실2) 6236
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
B = [int(input()) for _ in range(N)]
result = 0
start = max(B)
end = sum(B)
while start <= end :
mid = (start+end)//2
cnt = 1 #마지막꺼 안 세지니까 0이 아닌 1로 초기화
sum = 0
for i in range(N): #배열 다 돌면서 mid보다 sum이 작을 때를 카운트 해줌
sum += B[i]
if sum > mid :
cnt += 1
sum = B[i]
if cnt > M :
start = mid+1
else : #cnt가 M보다 작을 때 result값 갱신 해주고 값 더 올려서 반복
end = mid-1
result = mid
print(result)
24.랜선 자르기 (실2) 1654
import sys
input = sys.stdin.readline
K, N = map(int, input().split())
L = [int(input()) for _ in range(K)]
start = 1 #0으로 하면 mid가 0이 되어 0으로 나누는 경우가 생겨서 런타임 에러 뜸
end = max(L)
while start <= end :
mid = (start+end)//2
cnt = 0
for i in range(K):
cnt += L[i]//mid
if cnt < N :
end = mid-1
else : #cnt가 N보다 크거나 같은 경우 갱신해줌
start = mid+1
result = mid
print(result)
25.나무 자르기 (실2) 2805
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
T = list(map(int, input().split()))
start = 0
end = max(T)
while start <= end :
mid = (start+end)//2
total = 0
for i in range(N):
if T[i] > mid:
total += T[i]-mid
if total < M :
end = mid-1
else :
start = mid+1
result = mid
print(result)
💻230112~230118 (실2~실1)
26.차이를 최대로 (실2) 10819
import sys
from itertools import permutations
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
result = []
for per in list(permutations(A, N)):
ans = 0
for i in range(N-1):
ans += abs(per[i]-per[i+1])
result.append(ans)
print(max(result))
27.연산자 끼워넣기2 (실2) 15658
import sys
from itertools import permutations
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
O = list(map(int, input().split()))
#연산 함수
result = []
def operator(ans, n):
if n == N:
result.append(ans)
return
for i in range(4):
if O[i] > 0 :
O[i] -= 1
if i == 0:
operator(ans + A[n], n+1)
if i == 1:
operator(ans - A[n], n+1)
if i == 2:
operator(ans * A[n], n+1)
if i == 3:
operator(int(ans / A[n]), n+1)
O[i] += 1
operator(A[0], 1)
# 출력
print(max(result))
print(min(result))
28.로또 (실2) 6603
import sys
from itertools import combinations
input = sys.stdin.readline
while True :
S = list(map(int, input().split()))
k = S.pop(0)
if k == 0:
break
for com in list(combinations(S, 6)):
print(' '.join(map(str, com)))
print()
29.부등호 (실1) 2529
import sys
from itertools import permutations
input = sys.stdin.readline
k = int(input())
sign = list(map(str, input().split()))
num = [i for i in range(10)]
result = []
for per in list(permutations(num, k+1)):
f = 0
for i in range (k) :
if sign[i] == '<' and per[i] > per[i+1]:
f = 1
break
if sign[i] == '>' and per[i] < per[i+1]:
f = 1
break
if f == 0:
result.append(''.join(map(str, per)))
print(max(result))
print(min(result))
30.쿼드트리 (실1) 1992
import sys
input = sys.stdin.readline
N = int(input())
Q = [list(map(int, input().rstrip())) for _ in range(N)]
def dfs(x, y, n):
first = Q[x][y]
for i in range (x, x+n):
for j in range (y, y+n):
if Q[i][j] != first :
first = -1
break
if first == -1:
print("(", end='')
dfs(x, y, n//2)
dfs(x, y+n//2, n//2)
dfs(x+n//2, y, n//2)
dfs(x+n//2, y+n//2, n//2)
print(")", end='')
else :
if first == 0:
print("0", end='')
else :
print("1", end='')
if n == 1:
return
dfs(0, 0, N)
💻230119~230201 (실1~실1)
31. 컴백홈 (실1) 1189
import sys
input = sys.stdin.readline
R, C, K = map(int, input().split())
M = [input().rstrip() for _ in range(R)]
visited = [[0]*C for _ in range(R)]
visited[R-1][0] = 1
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def dfs(x, y, cnt):
global result
if x == 0 and y == C-1 :
if cnt == K:
result += 1
return
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < R and 0 <= ny < C and M[nx][ny] != 'T' and visited[nx][ny] == 0:
visited[nx][ny] = 1
dfs(nx, ny, cnt+1)
visited[nx][ny] = 0
result = 0
dfs(R-1, 0, 1)
print(result)
32. 연산자 끼워넣기 (실1) 14888
import sys
from itertools import permutations
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
O = list(map(int, input().split()))
#연산 함수
result = []
def operator(ans, n):
if n == N:
result.append(ans)
return
for i in range(4):
if O[i] > 0 :
O[i] -= 1
if i == 0:
operator(ans + A[n], n+1)
if i == 1:
operator(ans - A[n], n+1)
if i == 2:
operator(ans * A[n], n+1)
if i == 3:
operator(int(ans / A[n]), n+1)
O[i] += 1
operator(A[0], 1)
# 출력
print(max(result))
print(min(result))
33. 기타 레슨 (실1) 2343
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
L = list(map(int, input().split()))
start = max(L) # 0이 아님
end = sum(L)
while start <= end :
mid = (start+end)//2
# mid값에 따른 그룹 수 구하기
cnt = 1
total = 0
for i in L :
total += i
if total > mid:
cnt += 1
total = i
# 그룹 수가 M보다 작거나 같을 때 mid값을 result로 갱신
if cnt > M :
start = mid+1
else :
end = mid-1
result = mid
print(result)
34. 회전초밥 (실1) 2531
import sys
input = sys.stdin.readline
N, d, k, c = map(int, input().split())
S = [int(input()) for _ in range(N)]
result = 0
arr = S[0:k]
K = [0]*(d+1) #초밥 종류 배열
for i in range(k):
K[arr[i]] += 1
K[c] += 1
for i in range(N):
if (d+1)-K.count(0) > result: #배열K 에서 0이 아닌 것의 개수
result = (d+1)-K.count(0)
K[arr.pop(0)] -= 1 #첫 요소 삭제
arr.append(S[(i+k)%N]) #다음 요소 추가
K[S[(i+k)%N]] += 1
print(result)
35. 소수&팰린드롬 (실1) 1747
import sys
input = sys.stdin.readline
N = int(input())
while True:
n = list(map(int, str(N)))
#팰린드롬 검사
f1 = 0
for i in range(len(n)//2):
if n[i] != n[len(n)-i-1]:
f1 = 1
break
#팰린드롬 수일 때 소수 검사
f2 = 1
if f1 == 0:
#1일 때는 2가 출력되어야 함
if N == 1:
print(2)
break
#1이 아닐 때
f2 = 0
for i in range (2, N):
if N % i == 0:
f2 = 1
break
#팰린드롬 수이면서 소수일 때 출력
if f2 == 0:
print(N)
break
N += 1
💻2024~2025 (골5~골1)
36. 리모컨 (골5) 1107
• M이 0일 때, 100에서의 거리와 N의 자릿수 비교
• answer 초깃값을 100에서의 거리로 잡는다.
• 그 후 0부터 1,000,000까지 돌리면서 각 자릿수가 모두 arr에 없다면 answer를 갱신한다.
import sys
input = sys.stdin.readline
start = 100
N = int(input())
M = int(input())
if M:
arr = list(map(int, input().split()))
else:
print(min(abs(N-start), len(str(N))))
exit()
# 시작점에서 하나씩 가기
answer = abs(N-start)
# 0부터 1,000,000까지 다 돌리면서 answer 갱신하기
for i in range(1000001):
n = str(i)
cnt = 0
for j in range(len(n)):
if int(n[j]) in arr:
break
cnt += 1
if cnt == len(n):
answer = min(answer, len(n)+abs(N-i))
print(answer)
37. 두 용액 (골5) 2470
• 투포인터, 오름차순 정렬
• 합의 절댓값을 비교하며 0이면 break
• 0보다 크다면 end-1, 0보다 작다면 start+1을 계속 하여 0에 가깝게 만든다.
import sys
input = sys.stdin.readline
N = int(input())
arr = list(map(int, input().split()))
start = 0
end = N-1
arr.sort()
answer = [arr[start], arr[end]]
minValue = 2000000001
while start < end:
total = arr[start] + arr[end]
if abs(total) < abs(minValue):
answer = [arr[start], arr[end]]
minValue = arr[start] + arr[end]
if total == 0:
break
if total > 0:
end -= 1
else:
start += 1
print(*answer)
38. ⚾ (골4) 17281
40. 공유기 설치 (골4) 2110
41. N-Queen (골4) 9663
42. 색종이 붙이기 (골3) 17136
43. 가장 긴 증가하는 부분 수열2 (골2) 12015
44. k번째 수 (골1) 1300
댓글남기기