알얼알/0521

• 일곱 난쟁이
  
• 단지번호붙이기
  
• 연속합
  
• 내일 할거야
  
• 문자열
  
  

백준 그룹 내에 있던 해설인데 뒤늦게 위키에도 올려봅니다.

'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)

알얼알