IT-garden

문제

2차원 배열이 주어졌을 때 (i, j) 위치부터 (x, y) 위치까지에 저장되어 있는 수들의 합을 구하는 프로그램을 작성하시오. 배열의 (i, j) 위치는 i행 j열을 나타낸다.

입력

첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 합을 구할 부분의 개수 K(1 ≤ K ≤ 10,000)가 주어진다. 다음 K개의 줄에는 네 개의 정수로 i, j, x, y가 주어진다(i ≤ x, j ≤ y).

출력

K개의 줄에 순서대로 배열의 합을 출력한다. 배열의 합은 231-1보다 작거나 같다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍

정답

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

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

for i in range(1,n+1):
    for j in range(1,m+1):
        dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + a[i-1][j-1]

for s in range(k):
    i,j,x,y=map(int,input().split())
    print(dp[x][y]-dp[x][j-1]-dp[i-1][y] + dp[i-1][j-1])

dp[i][j]는 dp[1][1]부터 dp[i][j]까지의 합입니다.

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

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍
수학

정답

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

n=int(input())
a=list(map(int,input().split()))
a=[0]+a
dp=[0]*(n+1)
dp[1]=a[1]

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

print(max(dp[1:]))

n개의 정수 , 수열[자리번호]
n = 1 수열[1]
n = 2 수열[1] + 수열[2], 수열[2]
n = 3 수열[1] + 수열[2] + 수열[3], 수열[2] + 수열[3], 수열[3]
n = 4 수열[1] + 수열[2] + 수열[3] + 수열[4], 수열[2] + 수열[3] + 수열[4], 수열[3] + 수열[4], 수열[4]
의 경우의 수가 있습니다.

n = 2를 보면 수열[1] + 수열[2]는 n = 1의 경우에 두 번째 수열을 더하는 경우이고 수열[2]는 두 번째 수열의 값입니다.
따라서 점화식은 해당 n 위치의 값과 이전 dp값에 n 위치의 값을 더한 후 비교하는 경우 2가지로 볼 수 있습니다.
이를 통해 앞에서부터 수열의 각 위치까지 최대값을 구하고 전체 dp에서 최대값을 구하면 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합이 됩니다.

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

문제

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

1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.

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

입력

첫째 줄에 N이 주어진다.

출력

첫째 줄에 N자리 이친수의 개수를 출력한다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍

정답

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

n=int(input())

dp=[0]*(n+1)
dp[1]=1

if n == 2:
    dp[2]=1
elif n > 2:
    dp[2]=1
    for i in range(3,n+1):
        dp[i]=dp[i-2]+dp[i-1]

print(dp[n])

N = 1 이면 1

N = 2 이면 10

N = 3 이면 100, 101

N = 4 이면 1000, 1001, 1010

N = 5 이면 10000, 10001, 10010, 10100, 10101

이진수 중 이친수를 찾는 것이기 때문에 이친수는 0과 1로 이루어져 있습니다.

이진수는 0이나 1로 시작하는데 이친수는 0으로 시작할 수 없다고 했기 때문엔 0으로 시작하는 경우를 제외하고 이친수를 구했습니다.

N = 1 이면 1개, N = 2 이면 1개, N = 3 이면 2개, N = 4이면 3개, N = 5이면 5개

피보나치 수열의 점화식이 나옵니다.

dp[1] = 1 ,dp[2] = 1 , dp[n] = dp[n-1] + dp[n-2] (n이 3 이상인 경우)

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

문제

요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다.

PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다.

• 전설카드
• 레드카드
• 오렌지카드
• 퍼플카드
• 블루카드
• 청록카드
• 그린카드
• 그레이카드

카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다.

민규는 지난주에 너무 많은 돈을 써 버렸다. 그래서 오늘은 돈을 최소로 지불해서 카드 N개를 구매하려고 한다. 카드가 i개 포함된 카드팩의 가격은 Pi원이다.

예를 들어, 카드팩이 총 4가지 종류가 있고, P1 = 1, P2 = 5, P3 = 6, P4 = 7인 경우에 민규가 카드 4개를 갖기 위해 지불해야 하는 금액의 최솟값은 4원이다. 1개 들어있는 카드팩을 4번 사면 된다.

P1 = 5, P2 = 2, P3 = 8, P4 = 10인 경우에는 카드가 2개 들어있는 카드팩을 2번 사면 4원이고, 이 경우가 민규가 지불해야 하는 금액의 최솟값이다.

카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최솟값을 구하는 프로그램을 작성하시오. N개보다 많은 개수의 카드를 산 다음, 나머지 카드를 버려서 N개를 만드는 것은 불가능하다. 즉, 구매한 카드팩에 포함되어 있는 카드 개수의 합은 N과 같아야 한다.

입력

첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000)

둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)

출력

첫째 줄에 민규가 카드 N개를 갖기 위해 지불해야 하는 금액의 최솟값을 출력한다.

예제 입력과 출력

정답

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

n=int(input())
a=list(map(int,input().split()))
a=[0]+a
dp=a

for i in range(1,n+1):
    for j in range(1,i):
        print(i-j,j)
        dp[i]=min(dp[i],dp[i-j]+a[j])

print(dp[n])

dp[n]을 입력받은 리스트 a로 만듭니다. (ex. dp[2]=카드 2개를 2개팩으로 샀을 때의 가격)

dp[n]=
dp[n-1]+a[1]
dp[n-2]+a[2]
dp[n-3]+a[3]
dp[n-4]+a[4]
.
.
.
dp[1]+a[n-1] 중 가장 작은 값을 선택합니다.

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

문제

요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다.

PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다.

• 전설카드
• 레드카드
• 오렌지카드
• 퍼플카드
• 블루카드
• 청록카드
• 그린카드
• 그레이카드

카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다.

민규는 카드의 개수가 적은 팩이더라도 가격이 비싸면 높은 등급의 카드가 많이 들어있을 것이라는 미신을 믿고 있다. 따라서, 민규는 돈을 최대한 많이 지불해서 카드 N개 구매하려고 한다. 카드가 i개 포함된 카드팩의 가격은 Pi원이다.

예를 들어, 카드팩이 총 4가지 종류가 있고, P1 = 1, P2 = 5, P3 = 6, P4 = 7인 경우에 민규가 카드 4개를 갖기 위해 지불해야 하는 금액의 최댓값은 10원이다. 2개 들어있는 카드팩을 2번 사면 된다.

P1 = 5, P2 = 2, P3 = 8, P4 = 10인 경우에는 카드가 1개 들어있는 카드팩을 4번 사면 20원이고, 이 경우가 민규가 지불해야 하는 금액의 최댓값이다.

마지막으로, P1 = 3, P2 = 5, P3 = 15, P4 = 16인 경우에는 3개 들어있는 카드팩과 1개 들어있는 카드팩을 구매해 18원을 지불하는 것이 최댓값이다.

카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값을 구하는 프로그램을 작성하시오. N개보다 많은 개수의 카드를 산 다음, 나머지 카드를 버려서 N개를 만드는 것은 불가능하다. 즉, 구매한 카드팩에 포함되어 있는 카드 개수의 합은 N과 같아야 한다.

입력

첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000)

둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)

출력

첫째 줄에 민규가 카드 N개를 갖기 위해 지불해야 하는 금액의 최댓값을 출력한다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍

정답

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

n=int(input())
a=list(map(int,input().split()))
a=[0]+a
dp = [0]*(n+1)

for i in range(1,n+1):
    for j in range(1,i+1):
        dp[i]=max(dp[i],dp[i-j]+a[j])

print(dp[n])

dp[n]=
dp[n-1]+a[1]
dp[n-2]+a[2]
dp[n-3]+a[3]
dp[n-4]+a[4]
.
.
.
dp[n-n]+a[n] 중 가장 큰 값을 선택합니다.

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

문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

예제 입력과 출력

알고리즘 분류

BFS

정답

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

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

dx=[-1,0,1,0]
dy=[0,1,0,-1]

def bfs():
    de=deque()
    de.append([0,0,0])
    ch[0][0][0]= 1
    while de:
        x,y,z=de.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m:
                if a[nx][ny] == 0 and ch[nx][ny][z] == 0:
                    ch[nx][ny][z] = ch[x][y][z] + 1
                    de.append([nx,ny,z])
                elif a[nx][ny] == 1 and  z == 0 and ch[nx][ny][z+1] == 0: 
                    ch[nx][ny][z+1] = ch[x][y][z] +1
                    de.append([nx,ny,z+1])
                              
bfs()
if ch[n-1][m-1][0] != 0 and ch[n-1][m-1][1] != 0: # 벽을 거친 경우와 거치지 않은 경우 둘 다 가능한 경우
    print(min(ch[n-1][m-1][0],ch[n-1][m-1][1]))
elif ch[n-1][m-1][0] != 0: # 벽을 거치지 않은 경우만 가능한 경우
    print(ch[n-1][m-1][0])
elif ch[n-1][m-1][1] != 0: #벽을 거친 경우만 가능한 경우
    print(ch[n-1][m-1][1])
else: # 불가능한 경우
    print(-1)

배열 ch를 x좌표, y좌료, 부순 것 개수로 3차원으로 만듭니다.
기본 BFS에서 벽이 나왔는데 벽을 뚫은 적이 없는 경우 세번째 차수 값을 바꿔 ch에 저장하고 그 값을 큐에 넣습니다.
한번 BFS를 수행하고 벽을 거쳤을 때와 거치지 않은 것 중 최단 거리를 구합니다.

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