[백준/Algorithm] 9461, 1699, 2193

JiYeon Park·2021년 1월 13일
0

Algorithm

목록 보기
3/5
post-thumbnail

[백준 9461번] 파도반 수열

문제

풀이

문제에 삼각형 사진을 확인 시, 6번째 이후 부터는 삼각형 변의 길이는 n-1 번째와 n-5번째 삼각형의 변이 맞닿아있는 걸 확인 할 수 있습니다.
점화식을 통해 구할 수 있으며, 6번째 삼각형부터 규칙이 보이므로 배열에 [1, 1, 1, 2, 2] 를 선언하여 답을 구합니다.

n번째 삼각형 = n-1번째 삼각혐 + n-5번째 삼각형

python 코드

count = int(input())
seq = [0 for _ in range(101)]
for i in range(count):
  n = int(input())
  seq[1], seq[2], seq[3] = 1, 1, 1
  seq[4], seq[5] = 2, 2
  for j in range(6, n+1):
    seq[j] = seq[j-1] + seq[j-5];
  print(seq[n])

[백준 1699번] 제곱수의 합

문제

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.

주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.

풀이

제곱수의 합을 최소 개수로 표현하면 하기와 같은데 배열에 해당 수를 담고 점화식은 i가 숫자, j가 제곱수들이라고 했을때, arr[i] = min(dp[i - j]) + 1 입니다.

i = 16일때 i보다 작거나 같은 제곱수는 1, 4, 9, 16이므로
dp[i - 1], dp[i - 4], dp[i - 9], dp[i - 16]중 가장 작은 값은 0이고 여기에 1을 더한 값을 dp[i]에 넣어줍니다.

python 코드

n = int(input())
arr = [0 for i in range(n+1)]
square = [i * i for i in range(1, 317)]
for i in range(1, n + 1):
  s = []
  for j in square:
    if j > i:
        break
    s.append(arr[i - j])
  arr[i] = min(s) + 1
print(arr[n])

[백준 2193번] 제곱수의 합

문제

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.

이친수는 0으로 시작하지 않는다.
이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.
예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.

N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.

풀이

하기와 같이 규칙을 나열할 시에 n자리 이친수의 개수는 n-1자리 이친수 종류와 n-2 이친수 종류의 합으로 되어있는 걸 확인 할 수 있습니다.
그 이유는 n자리의 이친수의 개수를 구하기위해 하기와 이친수에 특성에 따라 하기와 같은 특성이 있기때문입니다.

  1. N-1자리 이친수 뒤에 0을 추가한 경우
  2. N-2자리 이친수 뒤에 01을 추가한 경우

N=1 : 1 (1가지)
N=2 : 10 (1가지)
N=3 : 101, 100 (2가지)
N=4 : 1010, 1000, 1001, (3가지)
N=5 : 10100, 10000, 10010, 10101, 10001 (5가지)
N=6 : 101000, 100000, 100100, 101010, 100010, 101001, 100001, 100101 (8가지)

python 코드

count = int(input())
arr = [0 for _ in range(91)]
arr[1], arr[2]  = 1, 1
for i in range(3, count+1):
  arr[i] = arr[i-1] +arr[i-2]
print(arr[count])
profile
열심히 공부중인 초보 개발자

0개의 댓글