IT-garden

문제 설명

제한조건

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

입출력 예

나의 풀이

def solution(triangle):
    for i in range(1,len(triangle)):
        triangle[i][0] += triangle[i-1][0]
        triangle[i][-1] += triangle[i-1][-1]
        for j in range(1,i):
            triangle[i][j] += max(triangle[i-1][j-1],triangle[i-1][j])
    
    return max(triangle[len(triangle)-1])

백준알고리즘 - 1932번 정수 삼각형 - 파이썬(Python)

위의 문제와 동일한 문제입니다.

프로그래머스 '정수 삼각형' : https://programmers.co.kr/learn/courses/30/lessons/43105

문제 설명

대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개의 나선 모양처럼 점점 큰 타일을 붙인 형태였다. 타일 장식물의 일부를 그리면 다음과 같다.

그림에서 타일에 적힌 수는 각 타일의 한 변의 길이를 나타낸다. 타일 장식물을 구성하는 정사각형 타일 한 변의 길이를 안쪽 타일부터 시작하여 차례로 적으면 다음과 같다.
[1, 1, 2, 3, 5, 8, .]
지수는 문득 이러한 타일들로 구성되는 큰 직사각형의 둘레가 궁금해졌다. 예를 들어, 처음 다섯 개의 타일이 구성하는 직사각형(위에서 빨간색으로 표시한 직사각형)의 둘레는 26이다.

타일의 개수 N이 주어질 때, N개의 타일로 구성된 직사각형의 둘레를 return 하도록 solution 함수를 작성하시오.

제한조건

• N은 1 이상 80 이하인 자연수이다.
  
  

입출력 예

나의 풀이

def solution(N):
    d=[0]*(N+1)
    d[1]=4
    d[2]=6
    for i in range(3,N+1):
        d[i] = d[i-1] + d[i-2]
    return d[N]

[1, 1, 2, 3, 5, 8 ...]일 때 타일의 개수가 주어지면 각 경우의 둘레를 구했습니다.

n = 1 이면 둘레는 1 * 4 = 4
n = 2 이면 둘레는 (1 * 2) + (2 * 2) = 6
n = 3 이면 둘레는 (3 * 2) + (2 * 2) = 10
n = 4 이면 둘레는 (5 * 2) + (3 * 2) = 16

이를 통해 n이 3이상인 경우 점화식 d[i] = d[i-1] + d[i-2]를 만들었습니다.

프로그래머스 '타일 장식물' : https://programmers.co.kr/learn/courses/30/lessons/43104

문제 설명

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

제한조건

• N은 1 이상 9 이하입니다.
• number는 1 이상 32,000 이하입니다.
• 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
• 최솟값이 8보다 크면 -1을 return 합니다.

입출력 예

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

나의 풀이

def solution(N, number):
    possible_set = [0,[N]] 
    if N == number: 
        return 1
    for i in range(2, 9): 
        case_set = [] 
        case_set.append(int(str(N)*i))
        for i_half in range(1, i//2+1):
            for x in possible_set[i_half]:
                for y in possible_set[i-i_half]: 
                    case_set.append(x+y)
                    case_set.append(x-y)
                    case_set.append(y-x)
                    case_set.append(x*y)
                    if y !=0:
                        case_set.append(x/y)
                    if x !=0:
                        case_set.append(y/x)
            if number in case_set:
                return i
            possible_set.append(case_set) 
    return -1

다이나믹 문제에서 문제를 어떤식으로 풀어야 할지 몰라 많이 시간을 사용했던 문제입니다.

프로그래머스 'N으로 표현' : https://programmers.co.kr/learn/courses/30/lessons/42895

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

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

출력

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

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍 

정답

import sys
input = lambda : sys.stdin.readline().strip()

a=input()
b=input()
li=[[0]*(len(b)+1) for i in range(len(a)+1)]

for i in range(1,len(a)+1):
    for j in range(1,len(b)+1):
        if a[i-1] == b[j-1]:
            li[i][j]=li[i-1][j-1]+1
        else:
            li[i][j]=max(li[i][j-1],li[i-1][j])

print(li[-1][-1])

백준 알고리즘 9251번 : www.acmicpc.net/problem/9251

문제

크리보드는 kriii가 만든 신기한 키보드이다. 크리보드에는 버튼이 4개만 있으며, 하는 역할은 다음과 같다.

1. 화면에 A를 출력한다.
2. Ctrl-A: 화면을 전체 선택한다
3. Ctrl-C: 전체 선택한 내용을 버퍼에 복사한다
4. Ctrl-V: 버퍼가 비어있지 않은 경우에는 화면에 출력된 문자열의 바로 뒤에 버퍼의 내용을 붙여넣는다.

크리보드의 버튼을 총 N번 눌러서 화면에 출력된 A개수를 최대로하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다.

출력

크리보드의 버튼을 총 N번 눌러서 화면에 출력할 수 있는 A 개수의 최댓값을 출력한다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍

정답

import sys
input = lambda : sys.stdin.readline().strip()

n=int(input())

dp = [i for i in range(0, 102)]

for i in range(6, 101):
    dp[i] = max(dp[i-3]*2, max(dp[i-4]*3, dp[i-5]*4))
    
print(dp[n])

백준 알고리즘 11058번 : https://www.acmicpc.net/problem/11058

문제

명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.

먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다.

각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다.

예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자.

• S = 1, E = 3인 경우 1, 2, 1은 팰린드롬이다.
• S = 2, E = 5인 경우 2, 1, 3, 1은 팰린드롬이 아니다.
• S = 3, E = 3인 경우 1은 팰린드롬이다.
• S = 5, E = 7인 경우 1, 2, 1은 팰린드롬이다.

자연수 N개와 질문 M개가 모두 주어졌을 때, 명우의 대답을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 N (1 ≤ N ≤ 2,000)이 주어진다.

둘째 줄에는 홍준이가 칠판에 적은 수 N개가 순서대로 주어진다. 칠판에 적은 수는 100,000보다 작거나 같은 자연수이다.

셋째 줄에는 홍준이가 한 질문의 개수 M (1 ≤ M ≤ 1,000,000)이 주어진다.

넷째 줄부터 M개의 줄에는 홍준이가 명우에게 한 질문 S와 E가 한 줄에 하나씩 주어진다.

출력

총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍 

정답

import sys
input = lambda : sys.stdin.readline().strip()

n=int(input())
a=list(map(int,input().split()))
m=int(input())
dp=[[0]*n for i in range(n)]

for i in range(n): # 길이가 1인 경우
    dp[i][i]=1

for i in range(n-1): # 길이가 2인 경우 
    if a[i] == a[i+1]:
        dp[i][i+1]=1

for i in range(1,n): # 길이가 3 이상인 경우
    for j in range(2,i+1):
        if a[i] == a[i-j] and dp[i-j+1][i-1] == 1:
            dp[i-j][i]=1
        
for i in range(m):
    s,e=map(int,input().split())
    print(dp[s-1][e-1])

백준 알고리즘 10942번 : https://www.acmicpc.net/problem/10942