leah

Input

첫째 줄에 게임을 진행하는 사람 A명이 주어진다. A는 2,000보다 작거나 같은 자연수이다.

둘째 줄에는 구하고자 하는 번째 T가 주어진다. (T ≤ 10000)

셋째 줄에는 구하고자 하는 구호가 “뻔”이면 0, “데기”면 1로 주어진다.

1
2
3
4
5
6
7

import sys
input = sys.stdin.readline

a = int(input())
t = int(input())
# w = 0(뻔) 1(데기)
w = int(input())

Brute Force

반복문이 중첩될 때는 어떤 반복문이 어떤 걸 담당하는지 정확히 해야한다.

• 게임이 1라운드 진행될 때마다 똑같은 형식의 점화식이 반복되어야 한다.

  • 새로운 배열을 생성하여 해당 라운드에 가능한 경우를 모두 저장한다.
  • 해당 라운드가 끝날 때까지 조건을 만족하는 경우가 없다면 배열의 길이만큼 진행 횟수를 더한다.

  1 2 3 4 5 6 7 8 9

  for i in range(1, t+1): ### t번째: 0 - 1 - 0 - 1 - 0 * (t-1) - 1 * (t-1) s = [0, 1, 0, 1] + [0]*(i+1) + [1]*(i+1) . . . ret += len(s)

• 해당 라운드의 배열을 하나씩 탐색해야 한다.

  • 만약 조건을 만족하는 경우가 있다면, 지금까지의 진행 횟수를 모두 더하여 인원 수만큼 나눈 나머지를 취하면 된다.

  1 2 3 4 5 6 7 8 9 10

  # p: number of person for p in range(len(s)): now = s[p] if now == w: count += 1 if count == t: print((ret + p) % a) exit(0)

Output

첫째 줄에 구하고자 하는 사람이 원탁에서 몇 번째에 있는지 정수로 출력한다.

1
2
3

if count == t:
  print((ret + p) % a)
  exit(0)

Input

첫째 줄에 정수 N과 K가 공백을 기준으로 구분되어 주어진다. (0≤N≤23, 0≤K≤9)

1
2
3
4
5

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
count = 0

Brute Force

• n시 59분 59초까지
• k가 시/ 분/ 초에 포함된 경우 count
• hidden case : k == 0인 경우
  • 시/ 분/ 초가 10보다 작을 경우 0을 붙여야 0 케이스 체크 가능

1
2
3
4
5
6
7
8

for h in range(n+1):
  for m in range(60):
    for s in range(60):
      check_hour = (str(k) in add_zero(h))
      check_min = (str(k) in add_zero(m))
      check_sec = (str(k) in add_zero(s))
      if check_hour or check_min or check_sec:
        count += 1

Output

00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 K가 하나라도 포함되는 시각들의 수를 출력한다.

1

print(count)

Input

정수 a, b, c, d, e, f가 공백으로 구분되어 차례대로 주어진다. (−999≤a,b,c,d,e,f≤999)

문제에서 언급한 방정식을 만족하는 (x,y)가 유일하게 존재하고, 이 때 x와 y가 각각 −999 이상 999 이하의 정수인 경우만 입력으로 주어짐이 보장된다.

1
2
3
4

import sys
input = sys.stdin.readline

f = list(map(int, input().split()))

Brute Force

pypy3으로 제출

• (x, y)는 유일함

1
2
3
4
5
6
7
8

for x in range(-999, 1000):
  for y in range(-999, 1000):
    check1 = (f[0] * x + f[1] * y == f[2])
    check2 = (f[3] * x + f[4] * y == f[5])

    if check1 and check2:
      print("%d %d" % (x, y))
      exit(0)

Output

문제의 답인 x와 y를 공백으로 구분해 출력한다.

1
2
3

if check1 and check2:
  print("%d %d" % (x, y))
  exit(0)

Input

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

1
2
3
4

import sys
input = sys.stdin.readline

n = int(input())

Brute Force

• n보다 작은 자연수이고
• 분해합이 같아야 함

1
2
3
4
5
6
7
8
9
10
11
12
13

for i in range(1, n):
  sum = i
  div = i

  while div // 10 > 0:
    sum += div % 10
    div = div // 10

  sum += div
  
  if sum == n:
    print(i)
    exit(0)

Output

첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다.

1
2
3
4
5

  if sum == n:
    print(i)
    exit(0)

print(0)

Input

첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다.

둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다.

합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.

1
2
3
4
5

import sys
input = sys.stdin.readline

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

Brute Force

• 3개의 합이 m과 가장 가까울 경우
• m을 넘지 않을 경우

1
2
3
4
5
6
7
8

ret = 0

for i in range(n-2):
  for j in range(i+1, n-1):
    for k in range(j+1, n):
      sum = s[i]+s[j]+s[k]
      if (m-sum) >= 0 and abs(m-sum) < abs(m-ret):
        ret = sum

Output

첫째 줄에 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력한다.

1

print(ret)

11066번과 동일한 문제이다. 허나 여느 DP 문제가 그렇듯 직접 풀어봐야 패턴 파악 가능

Input

첫째 줄에 행렬의 개수 N(1 ≤ N ≤ 500)이 주어진다.

둘째 줄부터 N개 줄에는 행렬의 크기 r과 c가 주어진다. (1 ≤ r, c ≤ 500)

항상 순서대로 곱셈을 할 수 있는 크기만 입력으로 주어진다.

1
2
3
4

import sys
input = sys.stdin.readline
n = int(input())
s = [list(map(int, input().split())) for _ in range(n)]

DP

1

dp = [[0]*n for _ in range(n)]

• 작은 단위부터 곱해나가야 하므로 gap 반복문 먼저 시행

  1	for gap in range(1, n):

• 이후 처음부터 곱해나가야 하므로 start 반복문 시행

  1	for start in range(n-1):

• end 범위 지정

  1 2 3

  end = start + gap if end >= n: break

• start 부터 gap 만큼 진행하며 dp값 갱신

  • dp를 0으로 초기화 시켰으므로 주어진 조건에 따라 최대값으로 세팅하고 갱신

  1 2 3

  dp[start][end] = 2 ** 31 for g in range(gap): dp[start][end] = min(dp[start][end], dp[start][start+g] + dp[start+g+1][end] + s[start][0]*s[start+g][1]*s[end][1])

Output

첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같다.

1

print(dp[0][-1])

Input

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20)

둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

1
2
3
4
5

import sys
input = sys.stdin.readline

r, c = map(int, input().split())
s = [list(map(lambda x: ord(x) - 65, input().strip())) for _ in range(r)]

ㅋㅋㅋ 이거… 이거 만만하게 보면 안 된다. 이번 문제는 알고리즘도, 코드도 쉬운데 입력 처리 때문에 1시간 날려먹음 ◡̈ 무조건! string이 아니라 ASCII 코드 이용해서 int로 변환해 저장해야 한다. ㅎㅎ

DFS

처음에는 BFS로 시도했으나.. DFS가 더 편할 것 같다는 판단에 수정했다. 내가 놓쳤던 부분이자 배운 부분은

• dfs 호출 전후로 스택과 같이 push, pop 구현하기

이다.

코드는 쉬움.

• 알파벳 방문이기 때문에 직전 문제처럼 알파벳 배열을 생성해서 방문 체크 하면 됨.

  1 2 3

  dir = [[-1, 0], [1, 0], [0, -1], [0, 1]] visited = [False]*(ord('a') - ord('A')) visited[s[0][0]] = True

• 최대값 출력이기 때문에 max 값 저장용으로 global 변수 를 이용한다.

  1 2 3 4 5 6 7 8

  ret = 1 . . . global ret if cnt > ret: ret = cnt

• 이 외에는 여느 때와 다름 없이, 범위 & 방문 체크. 여기서 조건 만족 시 바로 dfs 호출이 아니라 pop, push를 구현해야 한다! dfs 호출 전 push, dfs 호출이 끝나면 pop 해서 깊이 우선 탐색을 시행한다.

  1 2 3 4 5 6 7 8

  for d in dir: nx = i + d[0] ny = j + d[1] if 0 <= nx < r and 0 <= ny < c and not visited[s[nx][ny]]: visited[s[nx][ny]] = True dfs(nx, ny, cnt + 1) visited[s[nx][ny]] = False

Output

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

1
2

dfs(0, 0, 1)
print(ret)

Input

프로그램 입력은 T 개의 테스트 케이스로 구성된다. 테스트 케이스 개수 T 는 입력의 첫 줄에 주어진다.

각 테스트 케이스로는 두 개의 정수 A와 B(A ≠ B)가 공백으로 분리되어 차례로 주어지는데 A는 레지스터의 초기 값을 나타내고 B는 최종 값을 나타낸다. A 와 B는 모두 0 이상 10,000 미만이다.

1
2
3
4
5
6
7

from collections import deque
import sys
input = sys.stdin.readline
t = int(input())

for _ in range(t):
  a, b = map(int, input().split())

BFS

이 문제 접근 방식의 핵심은 가능한 숫자 0~9999의 index로 이루어진 visited 배열을 선언하고, dslr 4가지 경우를 체크하여 visited를 체크하는 것이다.

처음에는 무작정 4가지 경우의 수를

• 이미 있는 숫자의 위치만 바꾸면 되는 경우: L, R
• 그 외, 현재 숫자에 최종 숫자의 수가 없는 경우: D, S

로 나누어서 BFS로 풀었는데, 메모리 초과가 나버렸다. 그럴 수 밖에 없는게, DSLR 모든 경우를 매번 가능할 때마다 큐에 append 했기 때문..

진짜 많이 사용되는 방법이기 때문에 익혀두면 좋을 거다! 특히 숫자, 알파벳의 방문 여부를 체크하는 문제는 이 방식처럼 애초에 그를 이용해서 배열을 생성해놓으면 된다.

이것만 파악하면 코딩은 쉬움. (코드가 좀 귀엽다… ^.6..)

1
2
3

# arr에 방문 시 체크하면, 더 빨리 체크한 dslr 케이스가 진행된다.
arr = [0]*10000
print(bfs(a, b))

• dslr의 모든 조건을 체크하고, 만족하는 케이스를 큐에 넣어서 정답을 만날 때 break, 아니면 계속 모든 경우 체크 + 이어나가기 + breakpoint 체크를 반복하기 때문에 BFS이다.

• 큐 내의 조건문은 주어진 DSLR 조건에 따라 코딩하면 됨. 👈 코드가 귀엽다구.. 처음 시도했던 방식에서 디버깅 하느라 죽는 줄 알았는데, 정답이 귀여우니까 참내,, ^^

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

  def bfs(a, b): q = deque() q.append((a, "")) while q: n, dslr = q.popleft() dn = 2 * n % 10000 if dn == b: return dslr+"D" if not arr[dn]: arr[dn] = 1 q.append((dn, dslr+"D")) sn = n - 1 if n != 0 else 9999 if sn == b: return dslr+"S" if not arr[sn]: arr[sn] = 1 q.append((sn, dslr+"S")) ln = int(n % 1000 * 10 + n // 1000) if ln == b: return dslr+"L" if not arr[ln]: arr[ln] = 1 q.append((ln, dslr+"L")) rn = int(n % 10 * 1000 + n // 10) if rn == b: return dslr+"R" if not arr[rn]: arr[rn] = 1 q.append((rn, dslr+"R"))

Output

A에서 B로 변환하기 위해 필요한 최소한의 명령어 나열을 출력한다. 가능한 명령어 나열이 여러가지면, 아무거나 출력한다.

가능한 게 여러가지인데 아무거나 출력하라고 하면 그냥 정답 찾을 때 return 하면 된다. 다 출력하라고 하지 않는 이상 신경 안 써도 됨.

1

print(bfs(a, b))

분할 정복과 같이 접근하는 방식을 배웠다. 점화식을 세우기까지가 헬이고 세우면 코딩은 별 거 아님… 유용하게 쓰일 방식일 듯

Input

프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.

각 테스트 데이터는 두 개의 행으로 주어지는데, 첫 행에는 소설을 구성하는 장의 수를 나타내는 양의 정수 K (3 ≤ K ≤ 500)가 주어진다.

두 번째 행에는 1장부터 K장까지 수록한 파일의 크기를 나타내는 양의 정수 K개가 주어진다. 파일의 크기는 10,000을 초과하지 않는다.

1
2
3
4
5
6
7

import sys
input = sys.stdin.readline
t = int(input())

for _ in range(t):
  k = int(input())
  s = list(map(int, input().split()))

DP

어떻게 접근해야 하는지 막막했던 문제다. 일단 일반화를 어떻게 해야하지.. 싶었는데, 일단 정리해본 조건은

• 순서가 뒤바뀌면 안 됨
• 큰 수는 최소한으로 더하기 = 작은 수를 여러번 반복해서 더하게끔

이를 토대로 작성해본 조건식은 다음과 같다.

1
2
3
4
5

if s[i-1] > s[i] and s[i] < s[i+1]:
  if s[i-1] < s[i+1]:
    dp.append(s[i] + s[i-1])
  else:
    dp.append(s[i] + s[i+1])

결과적으로 정답과 크게 벗어나진 않는다. 다만 이 조건을 DP에 어떻게 적용하는가에서 헤맸다는 점?

일단 내가 놓친 부분은

• DP 배열이 2차원 배열이라는 것
• 반복문의 조건

이었다. Ci부터 Cj까지 더했을 때 최소값을 갱신하는 것이므로 min 을 사용하는 정도만 유추했지만, 이걸 어떻게 적용해야 할지 모르겠는 느낌. 갱신이므로 중첩 반복문이 들어갈 것이고, i번째 ~ j번째 의 최소값을 저장해야 하므로 2차원 배열을 사용한다.

1

dp = [[0]*k for _ in range(k)]

반복문을 다음과 같이 설정하면 된다.

• 작은 단위부터 시작해 점차 gap을 키우면서 start부터 end까지 dp 값을 갱신한다.

  1	for gap in range(1, k):

• dp[start][end] 는 부분 수열을 포함해 전체 수열까지 가능하다.

  1 2 3 4

  for start in range(k-1): end = start + gap if end == k: break

• dp를 0으로 세팅하고 갱신하는데, min을 사용하므로 현재 dp 값을 inf로 설정한다.

  1	dp[start][end] = sys.maxsize

• 그리고 gap만큼 start부터 증가시키면서 dp값을 갱신한다. 조건은

  • Ci~Cj까지 최소 축적합 = dp[i][j]
  • 점화식: dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]) + sum(s[i:j+1])

  1 2	for i in range(gap): dp[start][end] = min(dp[start][end], dp[start][start+i] + dp[start+(i+1)][end] + sum(s[start:end+1]))

  근데 여기서 재밌는 건, sum 을 쓰면 시간 초과가 뜬다는 점. 아래와 같이 딕셔너리 를 활용해 (sum의) 반복문을 줄여야 한다.

1
2
3

cumsum = {-1: 0}
for i in range(k):
  cumsum[i] = cumsum[i-1] + s[i]

1
2
3

for i in range(gap):
  # sum(s[start:end+1])
  dp[start][end] = min(dp[start][end], dp[start][start+i] + dp[start+(i+1)][end] + cumsum[end] - cumsum[start-1])

크누스 최적화

dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]) + sum(s[i:j+1]) 와 같은 점화식이 사용되는 DP 문제의 경우, 크누스 최적화 방식을 사용하여 시간복잡도를 **O(n^3)에서 O(n^2)**로 줄일 수 있다. 조건은

• A[i][j−1] ≤ A[i][j] ≤ A[i+1][j]
  • dp[i][k⋆] + dp[k⋆][j] 를 최소화하는 가장 작은 i<k⋆<j 의 A[i][j]
• C[a][c] + C[b][d] ≤ C[a][d] + C[b][c] (a≤b≤c≤d)
• C[b][c] ≤ C[a][d] (a≤b≤c≤d)

.

.

.

Output

프로그램은 표준 출력에 출력한다. 각 테스트 데이터마다 정확히 한 행에 출력하는데, 모든 장을 합치는데 필요한 최소비용을 출력한다.

1

sys.stdout.write(str(dp[0][k-1])+'\n')

쉬운 문제인 줄 알았으나 생각보다 복잡했던.. 그러나 방법을 찾으면 간단한.. 🤬

Input

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

1
2
3
4
5

import sys
input = sys.stdin.readline

str1 = "0" + input().strip()
str2 = "0" + input().strip()

DP

맨 처음 접근 방식은 중첩 for문을 돌면서 글자가 같으면 index를 동시에 증가시키고 이 작업을 반복한 후 최대 값을 출력하는 거였다. 근데 이렇게 하면 동일한 수열이 처음으로 만나는 글자부터가 아니라 중간에 만나는 글자부터 시작할 수 있기 때문에 아예 틀린 방식이 됨.

두번째는 방식은 맞는데 시간 초과가 떴다. 4중 for문을 돌렸기 때문^.< 아주 초과가 날 수 밖에… 그래도 접근 방식은 맞았다. 이 문제를 어떻게 풀어야 할지 제대로 파악하지 않고 접근했기 때문에 1번째 방식처럼 생각했던 거라, 제대로 어떻게 풀어야 할지부터 파악했다. dp를 2차원 배열로 생성해야 한다는 힌트만 얻고 풀어봤는데, 실제로 첫번째에서도 dp는 2차원 배열일 수 밖에 없었어서 조금만 더 생각해보면 이 힌트도 없어도 됐다. 암튼 조건을 더해보면,

• 각 string의 길이를 배열 크기로 설정해서 2차원 배열 dp을 만들고

  1	dp = [['']*len(str2) for _ in range(len(str1))]

• 2중 for문을 돌면서 동일한 글자일 시 dp[i-1][j-1] 에 저장되어 있는 str에 해당 글자를 더하면 된다.

  1 2 3 4

  for i in range(1, len(str1)): for j in range(1, len(str2)): if str1[i] == str2[j]: dp[i][j] = dp[i-1][j-1] + str1[i]

• 동일한 글자가 아니면 상/좌 dp 중 긴 str을 가져오면 된다.

  1 2 3 4 5

  else: if len(dp[i-1][j]) > len(dp[i][j-1]): dp[i][j] = dp[i-1][j] else: dp[i][j] = dp[i][j-1]

  결국 동일한 글자를 만나고 난 후에는 각 string의 index를 하나씩 증가시켜서 검사를 진행해야 하기 때문에, 꼭지점처럼 해당 index에 그때까지의 수열을 저장하게 된다.

Output

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를,

둘째 줄에 LCS를 출력한다.

LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.

1
2

print(len(dp[len(str1)-1][len(str2)-1]))
print(dp[len(str1)-1][len(str2)-1])