More actions
문제
해설
백준 그룹 내에 있던 해설인데 뒤늦게 위키에도 올려봅니다.
일곱 난쟁이
'Brute Force 브루트 포스'를 사용합시다. 이중 for문으로 난쟁이 2명을 선택하는 과정을 반복합니다. "9난쟁이 키의 합 - (2난쟁이 키의 합) = 100" 이 되면, 반복문을 나와 그 난쟁이들을 제외하고 '오름차순 정렬' 을 한 뒤 출력합니다.
x=[]
for i in range(9):
x.append(int(input()))
x.sort()
keySum=sum(x)
for i in range(8):
for j in range(i+1,9):
if keySum-x[i]-x[j]==100:
for k in range(9):
if k!=i and k!=j:
print(x[k])
exit()
단지번호붙이기
'BFS'를 사용합시다. 어떤 좌표에서 위, 아래, 오른쪽, 왼쪽으로 나아갈 수 있는데
arr[i][j] == 1 && visited[i][j] = false
(배열의 해당 위치에 집이 존재하고 방문하지 않은 곳) 이면, C++ 기준으로
queue<pair<int,int>>
로 선언된 큐에 push를 해줍니다. 이 작업을 큐가 빌 때까지 반복하는데 큐의 front를 이용해서 가능한 곳에 모두 접근할 수 있도록 합시다. 이 과정에서 큐에 push하거나 pop하는 경우 cnt를 늘려주면, 세대 수를 셀 수 있어요. 그럼 끝~ 마지막에 단지 별 세대수를 출력할 때는 꼭 '오름차순 정렬'을 적용해주세요! (이것때문에 고생많이 했어요ㅜ)
from collections import deque
def BFS(si,sj):
global N,X,visit
Q=deque()
Q.append((si,sj))
visit[si][sj]=True
cnt=1
while Q:
i,j=Q.popleft()
if i>0 and X[i-1][j] and not visit[i-1][j]:
Q.append((i-1,j))
visit[i-1][j]=True
cnt+=1
if i<N-1 and X[i+1][j] and not visit[i+1][j]:
Q.append((i+1,j))
visit[i+1][j]=True
cnt+=1
if j>0 and X[i][j-1] and not visit[i][j-1]:
Q.append((i,j-1))
visit[i][j-1]=True
cnt+=1
if j<N-1 and X[i][j+1] and not visit[i][j+1]:
Q.append((i,j+1))
visit[i][j+1]=True
cnt+=1
return cnt
N=int(input())
X,ans,visit=[],[],[[False]*N for i in range(N)]
for i in range(N):
X.append([*map(int,list(input()))])
for i in range(N):
for j in range(N):
if X[i][j] and not visit[i][j]:
ans.append(BFS(i,j))
ans.sort()
print(len(ans))
for i in ans:
print(i)
연속합
다이나믹 프로그래밍 문제입니다. 어떤 인덱스 x를 기준으로 최대의 연속합을 만드는 경우는 x-1 까지의 연속합에다 x 위치의 값을 더하는 경우, 또는 x 위치부터 새롭게 연속합을 시작하는 경우로 총 2가지가 있습니다. 따라서 점화식은
dp[x] = max(arr[x], dp[x-1] + arr[x]) n=int(input()) x=[*map(int,input().split())] dp=[0]*n dp[0]=x[0] for i in range(1,n): dp[i]=max(x[i],dp[i-1]+x[i]) print(max(dp))
내일 할거야
그리디스러운 방법으로 풀립니다. 과제 제출일이 늦은 과제부터 빠른 과제까지 루프를 돌면서 그때마다 가능한 한 과제 시작일을 뒤로 잡으면 됩니다. 여기서 가능하다는 말의 정의는 다른 과제와 겹치면 안 되고, 제출일 안에 끝나야 한다는 소리입니다. 참고로 파이썬은 입출력이 느려서 sys.stdin.readline을 썼습니다.
import sys
input=sys.stdin.readline
n=int(input())
x=[0]*n
for i in range(n):
x[i]=[*map(int,input().split())]
x.sort(key=lambda x:-x[1])
left=10**10
for i in range(n):
if x[i][1]<left:
left=x[i][1]-x[i][0]+1
else:
left=left-x[i][0]
print(left-1)
문자열
슬라이딩 윈도우 문제입니다. 범위가 작아서 이중 for문으로 완전탐색해도 풀립니다. 알파벳을 앞뒤로 추가한다고 하니까 어려워 보이지만 실제로 추가해볼 필요는 없습니다. 어차피 문자열 B와 동일하게 추가할거니까요. 그 점을 고려해보면 좋은 아이디어를 얻을 수 있는데, 반복문으로 문자열 A를 B의 특정 위치에 대보면서 차이가 최소가 될 때 정답이 됩니다.
a,b=input().split()
r=50
for i in range(len(b)-len(a)+1):
t=0
for j in range(len(a)):
if a[j]!=b[i+j]: t+=1
r=min(r,t)
print(r)