greentea31's Note

https://programmers.co.kr/learn/courses/30/lessons/82612

풀이 과정

탑승시 필요한 금액 = 기본 금액 * 탑승 횟수 임을 생각하면서 탑승 횟수에 따른 필요 금액의 누적 합과 보유 금액을 비교해주고 모자란 금액을 출력하거나 0을 출력해주면 된다.

소스 코드

def solution(price, money, count):
    answer = 0
    need_money = 0
    for ride_count in range(1, count+1):
        need_money += price * ride_count
    if need_money > money:
        answer = need_money - money
    return answer

https://programmers.co.kr/learn/courses/30/lessons/87389

풀이 과정

n을 x로 나눈 나머지가 1이 되도록 하는 가장 작은 자연수 x를 구하시오

1. n을 2부터 n-1까지 나눠보면서 나머지가 1이 될 때의 값을 출력해주면 된다.

2. n-1의 약수중 가장 작은 값을 출력해주면 된다. n-1이 소수이면 n-1을 출력해야 한다.

문제를 읽고 위의 2가지 방법이 떠올랐고 2번째 방법으로 문제를 해결하였다. 어떤 수 n의 약수를 구하려면 n을 2부터 rootn까지 나눠보고 나누어 떨어지면 약수라고 판정하면 된다.

소스 코드

def solution(n):
    n -= 1
    answer = n
    for i in range(2, int(n**(1/2)) + 2):
        if n % i == 0:
            answer = i
            break;
    return answer

https://programmers.co.kr/learn/courses/30/lessons/86491

풀이 과정

모든 명함을 담을 수 있는 가장 작은 지갑을 만들어야 하는데 명함은 회전해서 담을 수 있다.

4개의 명함이 있다고 하면 1 2 3 4, 12 13 14 23 24 34, 123 124 134 234, 1234 번째 명함을 회전시켜본 뒤 넓이를 구하고 가장 작은 값을 답으로 내는 방법을 떠올려봤지만 sizes의 길이가 10,000까지 들어오므로 이건 너무 시간이 오래 걸린다.

명함은 회전해서 담을 수 있으므로 가로, 세로 길이는 중요하지 않다. 긴 쪽의 길이와 짧은 쪽의 길이를 한 곳에 몰아넣은 다음, 긴 쪽의 길이 중에서 가장 큰 값 * 짧은 쪽의 길이 중에서 가장 큰 값을 해주면 답이 도출할 수 있다. 또한 이렇게 풀면 O(N)의 시간복잡도로 문제를 해결할 수 있다.

소스 코드

def solution(sizes):
    max_width, max_height = 0, 0
    for a, b in sizes:
        if a > b:
            a, b = b, a
        max_width = max(max_width, a)
        max_height = max(max_height, b)
    answer = max_width * max_height
    return answer

https://programmers.co.kr/learn/courses/30/lessons/12901

풀이 과정

1월 1일과 a월 b일이 몇 일 차이가 나는지 계산 후 나머지 연산을 통해 어떤 요일인지 출력해주면 된다. 각 월의 일수와 요일을 리스트에 저장하여 문제를 해결하였다.

소스 코드

def solution(a, b):
    wol = [0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
    week = ["FRI", "SAT", "SUN", "MON", "TUE", "WED", "THU"]

    answer = b - 1
    subwol = a - 1

    for i in range(subwol + 1):
        answer += wol[i]

    answer %= 7
    answer = week[answer]

    return answer

https://programmers.co.kr/learn/courses/30/lessons/68644 

풀이 과정

2중 for문으로 list를 순회하면서 리스트의 요소를 2개 더한 값들을 answer에 저장해주자. 만약 a라는 배열이 3개의 원소를 가지고 있다면

a[0] + a[1], a[0] + a[2], a[1] + a[2]를 다 answer에 더해주는 방식이다.

파이썬에서 set 자료형은 중복을 허용하지 않으므로 answer를 set 자료형으로 바꿔줘서 중복을 없앤 후, 다시 list 자료형으로 바꿔주고 sort() 메써드를 활용해서 오름차순으로 정렬하고 출력해주면 된다.

소스 코드

def solution(numbers):
    answer = []

    for number in range(len(numbers)):
        for number2 in range(number+1, len(numbers)):
            answer.append(numbers[number] + numbers[number2])

    answer = set(answer)
    answer = list(answer)
    answer.sort()
    return answer

https://programmers.co.kr/learn/courses/30/lessons/12982/

풀이 과정

최대한 많은 부서의 물품을 구매해 주려면 가장 적은 예산을 제출한 부서부터 결제해주면 된다.

그리디 방식으로 가장 작은 예산을 제출한 부서부터 결제해주면서 budget값을 체크해주고 answer를 늘려나가자.

소스 코드

def solution(d, budget):
    answer = 0
    d.sort()
    for department in d:
        if budget - department >= 0:
            answer += 1
            budget -= department
        else:
            break

    return answer

https://www.acmicpc.net/problem/2309

풀이 과정

9명중에 진짜 난쟁이를 7명 찾아야 하고 7명의 키의 합이 100이라 한다.

-> 모든 난쟁이의 키의 합을 구하고 9명중에 2명의 난쟁이의 키의 합을 뺐을 때 100이 나오면 그 2명은 진짜 난쟁이가 아니다

루프 2번 돌면서 9명중에 2명의 난쟁이를 고르는 수인 36번 돌다 보면 가짜 난쟁이 2명이 걸러진다 브루트 포스 방법으로 2명 뺐을 때 키의 합이 100이 나올때까지 다 찾아보면 된다.

키의 합을 구하는 연산 O(N), 가짜 난쟁이 2명을 찾는 연산 O(N^2)으로 총 O(N^3)의 시간복잡도를 갖고, N이 9이므로 그냥 다 해봐도 시간제한 내로 문제를 해결하는데 문제가 없다.

소스 코드

import sys
height = []

for i in range(9):
    height.append(int(sys.stdin.readline()))

height.sort()

sumHeight = sum(height)

fake1 = 0
fake2 = 0

for i in range(8):
    for j in range(i+1, 9):
        if sumHeight - height[i] - height[j] == 100:
            fake1 = i
            fake2 = j

for i in range(9):
    if i != fake1 and i != fake2:
        print(height[i])

https://www.acmicpc.net/problem/2133

풀이 과정

https://greentea31.tistory.com/26

위와 비슷하게 DP로 풀기 위해 점화식을 세워서 문제를 해결할 수 있다.

문제를 보고 생각을 하다보면 3x2 블록을 채우는 경우의 수는 3개가 있으니 3x4는 3x2 블록 2개 붙이면 되겠고... 이런 생각이 들겠지만 밑에 힌트를 보면 3x2 블록 채우는 경우의 수를 2개 조합한게 아닌 3x4 블록을 채우는 방법이 존재함을 알게 된다.

3xi 에서 i가 2씩 늘어날 수록 기존의 방법의 조합이 아닌 새로운 방법이 2개씩 더 추가된다.

따라서 d[i]를 3xi 블록을 채우는 방법의 경우의 수라고 하면

d[i] = 3 * d[i-2] + 2 * d[i-4] + 2 * d[i-6] + ... + 2 * d[0]이 성립한다.

d[0]은 1로 초기값을 설정해놔야 정답을 얻을 수 있다.

소스 코드

import sys

N = int(sys.stdin.readline())
d = [1, 0, 3, 0, 11]
for i in range(5, 31):
    d.append(3*d[i-2])
    for j in range(4, i+1, 2):
        d[i] += 2*d[i-j]

print(d[N])

https://greentea31.tistory.com/36

풀이 과정

https://greentea31.tistory.com/36

위의 연속합 문제에서 수열에서 수를 하나 제거할 수 있다는 조건이 추가된 문제이다. 

d[i]를 i번째 원소를 마지막으로 하는 가장 큰 연속합이라 하고, d2[i]를 i번째 원소에서 시작하는 가장 큰 연속합이라 하자. 그렇다면 i번째 원소를 제거했을 경우의 연속합을 구하면 d[i-1] + d2[i+1] 임을 알 수 있다.

d[i]의 점화식은 위의 문제를 풀어봤다면,

d[i] = d[i-1] + a[i] (d[i-1] > 0)

       = A[i] (d[i-1] <= 0) 임을 알 수 있고,

d2[i]의 점화식은 위의 점화식을 조금 변형한

d2[i] = d2[i+1] + a[i] (d2[i+1] >= 0)

         =  a[i] (d2[i+1] < 0) 임을 알 수 있다.

수열의 모든 원소 i에 대해 d[i], d[i-1] + d2[i+1]을 구해보고 구한 값들 중 가장 큰 값을 정답으로 출력해주면 된다.

소스 코드

import sys

n = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

d = [i for i in A]
d2 = [i for i in A]

for i in range(1, n):
    d[i] = max(d[i-1] + A[i], A[i])

for i in range(n-2, 1, -1):
    d2[i] = max(d2[i+1] + A[i], A[i])

max1 = max(d)
max2 = -1001

for i in range(1, n-1):
    max2 = max(max2, d[i-1] + d2[i+1])

print(max(max1, max2))

https://www.acmicpc.net/problem/11054

풀이 과정

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라 한다.

그렇다면 Sk를 기준으로 하는 바이토닉 수열의 길이는 Sk를 마지막으로 하는 증가하는 부분 수열의 길이 + Sk를 시작으로 하는 감소하는 부분 수열의 길이 - 1임을 알 수 있다.

따라서 주어진 수열의 모든 원소 K에 대해 K를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이 + K를 시작으로 하는 가장 긴 감소하는 부분수열의 길이 - 1을 구한 뒤, 가장 긴 값이 바로 가장 긴 바이토닉 부분 수열의 길이이다.

https://greentea31.tistory.com/34

https://greentea31.tistory.com/62

이 문제는 위의 2문제의 풀이법을 합쳐서 해결할 수 있는 문제이고 각 문제의 풀이를 위한 점화식은 위의 두 글을 참고하면 된다.

소스 코드

import sys

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

d = [1 for _ in range(N)]
d2 = [1 for _ in range(N)]

for i in range(N):
    for j in range(i):
        if A[j] < A[i]:
            d[i] = max(d[i], d[j] + 1)

for i in range(N-1, -1, -1):
    for j in range(N-1, i, -1):
        if A[j] < A[i]:
            d2[i] = max(d2[i], d2[j] + 1)

d3 = [d[i] + d2[i] - 1 for i in range(N)]

print(max(d3))