코딩묻은 디자이너

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

문제

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

출력

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

풀이

단순히 숫자를 배열에 입력해둔 후 i번째 수 부터 j번째 수 까지의 합을 구하면 시간초과가 난다.

N개의 숫자를 받아왔을 때 그 숫자를 처음부터 끝까지 돌며 모든 수의 누적 합을 미리 배열에 저장해두었다.

그리고 j번째의 누적 합과 i - 1번째의 누적합을 빼면 원하는 값을 얻을 수 있었다!

python코드

# 11659 구간 합 구하기 4
import sys

N, M = map(int,sys.stdin.readline().split())
arr = list(map(int,sys.stdin.readline().split()))
accrue = [0]

for n in range(N):
    accrue.append(arr[n] + accrue[n])
# print(accrue)
for tc in range(M):
    x, y = map(int,sys.stdin.readline().split())
    print(accrue[y] - accrue[x - 1])

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

문제

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

풀이

DP로 풀이해야하는 코드

2022.07.26 - [study/백준] - [백준] 11726. 2xn타일링 : python

와 같은 문제지만 2x2 종이가 추가되었다는게 다른점

2x2종이 한장이 1x2로 만들 수 있는 방법이 2가지라는 점을 명시하고 규칙을 찾아나갔다

2 = 3가지

3 = 5가지

4 = 11가지

5 = 21가지

.

.

.

숫자가 1 늘어날 때 가짓수가 확확 늘어나서 규칙을 찾기 어려웠다

규칙은 전의 수 + 전전의 수 * 2!

python 코드

# 11727 2xn 타일링 2

n = int(input())
arr = [0, 1, 3]

for i in range(3,n+1):
    arr.append((arr[i - 2] * 2) + arr[i - 1])

print(arr[n] % 10007)

python recursive 코드

def recursive(x):
    if x == 1:
        return 1
    if x == 2:
        return 3
    if arr[x] == 0:
        arr[x] = (recursive(x -2) * 2) + recursive(x-1)
    return arr[x]

n = int(input())
arr = [0] * (n+1)
print(recursive(n) % 10007)

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

문제

아래 <그림 1>과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다.

전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다.

전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 <그림 2>의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.

위와 같은 규칙에 따라 잘랐을 때 <그림 3>은 <그림 1>의 종이를 처음 나눈 후의 상태를, <그림 4>는 두 번째 나눈 후의 상태를, <그림 5>는 최종적으로 만들어진 다양한 크기의 9장의 하얀색 색종이와 7장의 파란색 색종이를 보여주고 있다.

입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다.

출력

첫째 줄에는 잘라진 햐얀색 색종이의 개수를 출력하고, 둘째 줄에는 파란색 색종이의 개수를 출력한다.

풀이

컬러를 비교하며 컬러값이 바뀌면 시작 값과 시작값에서 부터 진행되어야 하는 값을 바꿔가며 재귀로 돌아가게 만들었다

값이 다를 경우 4개로 분기되는데 이때 시작값은 (x,y) (x, y + n/2) (x + n/2, y) (x + n/2, y + n/2)값! 그리고 나눠질 때 마다 해당 사각형의 크기는 n/2가 된다

python 코드

# 2630 색종이 만들기
def check(a,b,n):
    global white, blue
    color = arr[a][b]
    for i in range(a,a+n):
        for j in range(b,b+n):
            if color != arr[i][j]:
                check(a,b,n//2)
                check(a+n//2,b,n//2)
                check(a,b+n//2,n//2)
                check(a+n//2,b+n//2,n//2)
                return
    if color == 1:
        blue += 1
    else:
        white += 1



n = int(input())
arr = [list(map(int,input().split())) for _ in range(n)]

white = 0
blue = 0

check(0, 0, n)

print(white)
print(blue)

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

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

풀이

n = int(input())
arr = [0] * (n + 3)

arr[2] = 2
arr[3] = 3
for i in range(4,n+1):
    arr[i] = arr[i - 1] + arr[i - 2]
print(arr[n] % 10007)

위의 코드는 예제는 다 맞고,,, 1과 같은 수가 들어오는 경우까지 생각해서 코드를 짰는데 실패였다

그래서 아래와 같이 코드를 새로 짜봤다

항상 arr[i - 1] + arr[i -2] 값을 새롭게 배열에 append 해주는 식으로 식을 짜고 입력인 1000까지기 때문에 for문은 3에서 1001까지 돌았다. 

python 코드

# 11726 2xn 타일링

arr = [0, 1, 2]

n = int(input())

for i in range(3,1001):
    arr.append(arr[i - 1] + arr[i - 2])
print(arr[n] % 10007)

python recursive 코드

import sys
sys.setrecursionlimit(10**6)

def recursive(x):
    if x == 1:
        return 1
    if x == 2:
        return 2
    if arr[x] == 0:
        arr[x] = recursive(x - 1) + recursive(x -2)
    return arr[x]
n = int(input())
arr = [0] * (n+1)
print(recursive(n) % 10007)

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

문제

오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.

파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100)

출력

각 테스트 케이스마다 P(N)을 출력한다.

풀이

규칙을 찾아서 풀어낸다.

처음에는 이미 주어진 첫 숫자 10개를 배열에 미리 입력한 후

P[N] = P[i-1] + P[i - 5]

로 처리하려고 했는데 

P[N] = P[i - 2] + P[i - 3]으로도 처리할 수 있어 그 방식으로 풀었다

2022.07.24 - [study/백준] - [백준] 9095. 1, 2, 3 더하기 : python

DP문제를 연속으로 풀어보니 규칙 찾기가 점점 쉬워진다!

python코드

# 9461 파도반 수열

T = int(input())

for tc in range(T):
    N = int(input())
    P = [0] * (N + 3)
    P[0] = 1
    P[1] = 1
    P[2] = 1

    for i in range(3, N):
        P[i] = P[i - 3] + P[i - 2]
        # print(P)
    print(P[N - 1])

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

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

풀이

2022.07.23 - [study/백준] - [백준] 1463. 1로 만들기 : python

어제의 문제와 비슷한 방법으로 규칙을 찾아서 풀었다.

한번 규칙을 찾는 방법을 알고 나니 어렵지 않게 찾을 수 있었다

1의 경우 : 1  ▶ 1

2의 경우 : 1 + 1 / 2 ▶ 2

3의 경우 : 1 + 1 + 1 / 1 + 2 / 2 + 1 / 3 ▶ 4

4의 경우 : 1 + 1 + 1 + 1 / 1 + 1 + 2 / 1 + 2 + 1 / 2 + 1 + 1 / 2 + 2 / 3 + 1 / 1 + 3 ▶ 7

5의 경우 : 1 + 1 + 1 + 1 + 1 / 1 + 1 + 1 + 2 / 1 + 1 + 2 + 1 / 1 + 2 + 1 + 1 / 2 + 1 + 1 + 1 / 2 + 2 + 1 / 2 + 1 + 2 / 1 + 2 + 2 / 1 +1 +3 / 1 + 3 + 1 / 3 + 1 + 1 / 2 + 3 / 3 + 2 ▶ 13

.

.

.

이런식으로 이어지다보면

4는 1의 경우 + 2의 경우 + 3의 경우

5는 2의 경우 + 3의 경우 + 4의 경우 로 진행된다는걸 알 수 있다

N[i] = N[i - 1] + N[i - 2] + N[i - 3]

식을 도출 할 수 있었는데

초기 1, 2, 3의 경우는 기본 값으로 입력을 받은 후 더해주도록 하였다.

만약 1이나 2나 3이 입력될 수도 있으므로 배열의 길이는 +3 해주었다

코드는 매우 간단하다

python코드

# 9095 1, 2, 3 더하기

T = int(input())

for tc in range(T):
    n = int(input())
    N = [0] * (n + 3)
    N[1] = 1
    N[2] = 2
    N[3] = 4

    for i in range(4, n+1):
        N[i] = N[i - 1] + N[i - 2] + N[i - 3]

    print(N[n])

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

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

풀이

처음에는 1이 될 때 가지 while문을 돌며 연산을 수행하도록 코드를 짜보았다

X = int(input())
cnt = 0

while X != 1:
    if X % 3 == 0:
        X = X // 3
        cnt += 1
    if X % 2 == 0:
        X = X // 2
        cnt += 1
    else:
        X -= 1
        cnt += 1
    print(X)
print(cnt)

이렇게 코드를 짜면 예제의 10만 입력해도

10 -> 5 -> 4 -> 3 -> 1 로 4번의 연산과정을 거치게 된다.

DP로 코드를 풀어야 했는데 그 과정을 이해하는게 너무 어려웠다

일단 입력값이 1 인 경우 이미 1이기 때문에 연산과정은 0이다

2인 경우 1을 빼는 방법과 2를 나누는 과정을 통해 1을 만들고 연산과정은 1이다

3인 경우 3으로 나누어 연산과정은 1이 된다

4인 경우 2로 난거나 1을 뺀다(+1) 그리고 2나 3은 각 각 연산과정이 1개 이므로 4인 경우 연산과정은 2가 된다

5인 경우 1을 빼는 연산과정을 거치고 (+1) 4는 이미 2번의 연산 과정을 가지고 있기 때문에 연산과정은 3이 된다

6인 경우 나누기 연산과정을 거치고(+1) 2 또는 3은 1번의 연산과정을 가지고 있으므로 연산과정은 2가 된다

.

.

.

이런 식으로 앞의 연산 과정이 가진 수를 토대로 값을 구해나가야 한다!

2나 3으로 나눠지지 않는 수는 1을 빼서 앞의 수로 만들어 준 후 연산과정을 계산해야하므로

arr[i - 1] + 1과정을 매번 거친다

만약 나눠질 경우 나눠진 숫자로 만든 후 연산과정을 계산하므로 3혹은 2로 나눠주었다!

python 코드

x = int(input())
arr = [0] * (x + 1)

for i in range(2, x+1):
    arr[i] = arr[i - 1] + 1

    if i % 3 == 0:
        arr[i] = min(arr[i],arr[i//3] + 1)
    if i % 2 == 0:
        arr[i] = min(arr[i],arr[i//2] + 1)

    print(arr)
print(arr[x])

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

문제

2019 HEPC - MAVEN League의 "비밀번호 만들기"와 같은 방식으로 비밀번호를 만든 경민이는 한 가지 문제점을 발견하였다. 비밀번호가 랜덤으로 만들어져서 기억을 못 한다는 것이었다! 그래서 경민이는 메모장에 사이트의 주소와 비밀번호를 저장해두기로 했다. 하지만 컴맹인 경민이는 메모장에서 찾기 기능을 활용하지 못하고 직접 눈으로 사이트의 주소와 비밀번호를 찾았다. 메모장에 저장된 사이트의 수가 늘어나면서 경민이는 비밀번호를 찾는 일에 시간을 너무 많이 쓰게 되었다. 이를 딱하게 여긴 문석이는 경민이를 위해 메모장에서 비밀번호를 찾는 프로그램을 만들기로 결심하였다! 문석이를 도와 경민이의 메모장에서 비밀번호를 찾아주는 프로그램을 만들어보자.

입력

첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다.

두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번호가 공백으로 구분되어 주어진다. 사이트 주소는 알파벳 소문자, 알파벳 대문자, 대시('-'), 마침표('.')로 이루어져 있고, 중복되지 않는다. 비밀번호는 알파벳 대문자로만 이루어져 있다. 모두 길이는 최대 20자이다.

N+2번째 줄부터 M개의 줄에 걸쳐 비밀번호를 찾으려는 사이트 주소가 한줄에 하나씩 입력된다. 이때, 반드시 이미 저장된 사이트 주소가 입력된다.

출력

첫 번째 줄부터 M개의 줄에 걸쳐 비밀번호를 찾으려는 사이트 주소의 비밀번호를 차례대로 각 줄에 하나씩 출력한다.

풀이

리스트로 풀면 시간 초과가 난다.

딕셔너리를 사용하면 간단히 풀 수 있다.

python 코드

# 17219 비밀번호 찾기
import sys

N, M = map(int, sys.stdin.readline().split())
passwordList = {}

for n in range(N):
    site ,password = sys.stdin.readline().split()
    passwordList[site] = password

# print(passwordList)

for m in range(M):
    site = sys.stdin.readline().strip()
    print(passwordList[site])

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

문제

김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다.

듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.

출력

듣보잡의 수와 그 명단을 사전순으로 출력한다.

풀이

처음엔 리스트를 만들어서 풀었으나 시간초과로 set()을 사용하여 풀었다.

듣보잡의 수와 그 명단을 '사전순'으로 출력한다. 의 사전순을 못봐서 계속 틀렸었다...

python코드

# 1764 듣보잡
import sys

N, M = map(int,sys.stdin.readline().split())
# 듣도 못한 사람
nohear = set()
# 보도 듣도 못한 사람
ans = set()

# 듣도 못한 사람을 받는다
for n in range(N):
    nohear.add(sys.stdin.readline().strip())
# 보도 못한 사람이 듣도 못한 리스트에 있는 경우 보도 듣도 못한 사람에 추가한다
for m in range(M):
    nolook = sys.stdin.readline().strip()
    if nolook in nohear:
        ans.add(nolook)
# 정렬
print(len(ans))
ans = sorted(list(ans))

# print(ans)
for i in ans:
    print(i)

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

문제

다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

• fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
• fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
• 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
• fibonacci(0)은 0을 출력하고, 0을 리턴한다.
• fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
• 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
• fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

출력

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

풀이

처음에는 문제에서 주어진 재귀로 접근해서 문제를 풀려고 했는데 시간초과가 나서 다른 방법을 찾아보았다.

https://jiwon-coding.tistory.com/28

흑흑 혼자서 풀이 방법을 찾기 어려워서 위의 블로그를 참고해 문제를 풀었다ㅠ

틀린 python코드

# 1003 피보나치 함수
import sys

def fibo(n):
    global zerocnt, onecnt
    if n == 0:
        zerocnt += 1
        return 0
    elif n == 1:
        onecnt += 1
        return 1
    else:
        return fibo(n - 1) + fibo(n - 2)

T = int(sys.stdin.readline())

for tc in range(T):
    N = int(sys.stdin.readline())
    zerocnt = 0
    onecnt = 0

    fibo(N)
    print('{} {}'.format(zerocnt, onecnt))

맞은 python 코드

# 1003 피보나치 함수
import sys

T = int(sys.stdin.readline())

for tc in range(T):
    N = int(sys.stdin.readline())
    zerocnt = [1, 0]
    onecnt = [0, 1]

    if N > 1:
        for i in range(N-1):
            zerocnt.append(onecnt[-1])
            onecnt.append(zerocnt[-2] + onecnt[-1])

    print('{} {}'.format(zerocnt[N], onecnt[N]))