EDOC 2023-2 2주차 과제

03-2. 구간 합

 

003. 구간 합 구하기 4 (백준 11659번)

 

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

 

from sys import stdin

n, m = map(int, stdin.readline().split())
data = list(map(int, stdin.readline().split()))

sum = [0]
temp = 0

for k in range(0, n):
    temp += data[k]
    sum.append(temp)

for k in range(0, m):
    i, j = map(int, stdin.readline().split())
    print(sum[j] - sum[i-1])

 

(정답) 참고로 나는 숫자 리스트에는 data[0]부터 첫번째 값을 차례로 넣었고, 합 리스트에는 sum[0]에는 0을 넣고 sum[1]부터 합들을 차례로 넣었다.

 

---

 

004. 구간 합 구하기 5 (백준 11660번)

 

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

 

from sys import stdin

n, m = map(int, stdin.readline().split())
data = []

for _ in range(0, n):
    data.append(list(map(int, stdin.readline().split())))

sum = [[0] * (n+1)]
for i in range(1, n+1):
    sum.append([0])
    for j in range(1, n+1):
        sum[i].append(sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + data[i-1][j-1])

for _ in range(0, m):
    x1, y1, x2, y2 = map(int, stdin.readline().split())
    print(sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1])

 

(정답) 구간 합을 이전 문제에서는 1차원 리스트로 구현했다면, 이 문제에서는 그대로 2차원 리스트로 구현한 것이다. 2차원에서의 합 리스트의 정의는 다음과 같다. sum[x][y] = data의 (0, 0)부터 (x, y)까지의 합. 이 정의에 입각하여 합 리스트 sum을 전부 채워주고, 합 리스트를 이용해서 구간 합을 구하기만 하면 끝난다. 식만 잘 세우면 구현 자체는 어렵지 않았다. 참고로 나는 숫자 리스트에는 data[0][0]부터 첫번째 값을 차례로 넣었고, 합 리스트에는 sum의 맨 왼쪽과 맨 위쪽 원소들은 0으로 채우고 sum[1][1]부터 합들을 차례로 넣었다. 

 

---

 

005. 나머지 합 (백준 10986번)

 

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

 

from sys import stdin

def combination(n, r):
    if n == 0:
        return 0
    
    num, den = 1, 1

    for i in range(r+1, n+1):
        num *= i
    for i in range(1, n-r+1):
        den *= i

    ans = int(num/den)

    return ans

n, m = map(int, stdin.readline().split())
data = list(map(int, stdin.readline().split()))

sum = [0]
temp = 0
count = [0] * m
count[0] = 1

for i in range(0, n):
    temp += data[i]
    temp %= m
    sum.append(temp)

    count[sum[i+1]] += 1

ans = 0

for i in range(0, m):
    ans += combination(count[i], 2)

print(ans)

 

교재에서는 0인 개수를 따로 더하고, 값이 같은 게 몇개인지 세어서 nCr 계산하여 더하는 것 같았다. (그리고 교재에서는 합배열 sum[0]부터 바로 합들을 넣어주었다.) 나는 합 배열 sum[0]에는 0을 넣고 sum[1]부터 합들을 넣어주었다. 그리고 0인 개수를 따로 더하는 과정 없이 값이 같은 게 몇개인지 세어서 nCr 계산하여 더해주기만 했다. 그러나 시간 초과 뜸. (오답)

 

from sys import stdin

n, m = map(int, stdin.readline().split())
data = list(map(int, stdin.readline().split()))

sum = [0]
temp = 0
count = [0] * m
count[0] = 1

for i in range(0, n):
    temp += data[i]
    temp %= m
    sum.append(temp)

    count[sum[i+1]] += 1

ans = 0

for i in range(0, m):
    ans += int(count[i]*(count[i]-1)/2)

print(ans)

 

첫번째 풀이에서는 조합 함수를 따로 만들어서 계산을 했는데 생각해보니 조합 계산들이 전부 nCr로 r이 고정되어 있었고, r이 2처럼 작은 값의 경우에는 대부분이 약분이 되므로 조합 함수 내용처럼 계산하는 것보다 두번째 풀이처럼 계산하는 것이 훨씬 효율적이다. (정답) 와 첫 골드 문제..!!! 교재가 다 한 것 같지만 그래도 뿌듯.. ㅎㅎㅎ

 

---

03-3. 투 포인터

 

006. 수들의 합 5 (백준 2018번)

 

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

 

from sys import stdin

n = int(stdin.readline())
count = 0

startIndex = 1
endIndex = 1
sum = 0

while startIndex <= n:
    if sum < n:
        sum += endIndex
        endIndex += 1
    elif sum > n:
        sum -= startIndex
        startIndex += 1
    else:
        count += 1
        sum += endIndex
        endIndex += 1

print(count)

 

처음에는 이중 반복문을 써서 시간 초과가 떴다. 책을 보고 다시 생각해서 해결했다. (정답)

 

---

 

007. 주몽 (백준 1940번)

 

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

 

from sys import stdin

n = int(stdin.readline())
m = int(stdin.readline())
mat = list(map(int, stdin.readline().split()))

mat.sort()

count = 0
index1 = 0
index2 = n-1
sum = 0

while index1 < index2:
    sum = mat[index1] + mat[index2]
    if sum < m:
        index1 += 1
    elif sum > m:
        index2 -= 1
    else:
        count += 1
        index1 += 1
        index2 -= 1
    
print(count)

 

(정답)

 

---

 

008. 좋다 (백준 1253번)

 

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

 

from sys import stdin

def greatNum(data, index1, index2, num):
    while index1 < index2:
        sum = data[index1] + data[index2]
        if sum < num:
            index1 += 1
        elif sum > num:
            index2 -= 1
        else:
            return True
    return False

n = int(stdin.readline())
data = list(map(int, stdin.readline().split()))
count = 0

data.sort()

if n >= 3 and data[2] == 0:
    count += 2

for i in range(1, n):
    if greatNum(data, 0, i-1, data[i]):
        count += 1

print(count)

 

처음에는 data[i]가 좋은 수인지 판단할 때는 data[0]부터 data[i-1]까지만 체크하는 방식으로 코드를 짰다. 수들이 전부 0 또는 양수일 때는 다 잘 되는 듯 했으나 음수가 포함되어 있는 경우에서 오류가 발생함을 알게 되었다. (역시 질문게시판 최고.. ㅎㅎ) (오답)

 

from sys import stdin

n = int(stdin.readline())
data = list(map(int, stdin.readline().split()))
count = 0

data.sort()

for i in range(0, n):
    index1 = 0
    index2 = n-1
    num = data[i]

    while index1 < index2:
        sum = data[index1] + data[index2]
        if sum < num:
            index1 += 1
        elif sum > num:
            index2 -= 1
        else:
            if index1 == i:
                index1 += 1
            elif index2 == i:
                index2 -= 1
            else:
                count += 1
                break

print(count)

 

음수가 있을 경우까지 포함시키기 위해 그냥 모든 수에 대해 data[0]부터 data[n-1]까지 체크하는 코드로 수정하였다. (정답)

 

---

03-4. 슬라이딩 윈도우

 

009. DNA 비밀번호 (백준 12891번)

 

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

 

from sys import stdin

s, p = map(int, stdin.readline().split())
data = stdin.readline().strip()

chk = list(map(int, stdin.readline().split()))
cur = [0] * 4
cnt = 0
start = 0

for i in range(0, p):
    if data[i] == 'A':
        cur[0] += 1
    elif data[i] == 'C':
        cur[1] += 1
    elif data[i] == 'G':
        cur[2] += 1
    elif data[i] == 'T':
        cur[3] += 1
    
while start+p <= s:
    isSafe = True
    for j in range(0, 4):
        if cur[j] < chk[j]:
            isSafe = False
            break
    if isSafe:
        cnt += 1

    if start+p == s:
        break
    
    if data[start] == 'A':
        cur[0] -= 1
    elif data[start] == 'C':
        cur[1] -= 1
    elif data[start] == 'G':
        cur[2] -= 1
    elif data[start] == 'T':
        cur[3] -= 1

    if data[start+p] == 'A':
        cur[0] += 1
    elif data[start+p] == 'C':
        cur[1] += 1
    elif data[start+p] == 'G':
        cur[2] += 1
    elif data[start+p] == 'T':
        cur[3] += 1

    start += 1

print(cnt)

 

(정답)

 

from sys import stdin

def match(c):
    if c == 'A':
        return 0
    elif c == 'C':
        return 1
    elif c == 'G':
        return 2
    elif c == 'T':
        return 3
    else:
        return -1

s, p = map(int, stdin.readline().split())
data = stdin.readline().strip()

chk = list(map(int, stdin.readline().split()))
cur = [0] * 4
cnt = 0
start = 0

for i in range(0, p):
    cur[match(data[i])] += 1
    
while start+p <= s:
    isSafe = True
    for j in range(0, 4):
        if cur[j] < chk[j]:
            isSafe = False
            break
    if isSafe:
        cnt += 1

    if start+p == s:
        break
    
    cur[match(data[start])] -= 1
    cur[match(data[start+p])] += 1

    start += 1

print(cnt)

 

앞의 풀이도 정답이긴 하지만 코드가 너무 지저분해서 문자를 확인하는 부분을 함수로 만들어서 간결하게 만들었다. (정답)

 

---

 

010. 최솟값 찾기 (백준 11003번)

 

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

 

from sys import stdin
from collections import deque

n, l = map(int, stdin.readline().split())
data = list(map(int, stdin.readline().split()))

window = deque()

for i in range(0, l):
    window.append(data[i])
    print(min(window), end=" ")

for i in range(l, n):
    window.popleft()
    window.append(data[i])
    print(min(window), end=" ")

 

당연하게도 (??) 시간 초과가 떴다. (오답)

 

from sys import stdin
from collections import deque

n, l = map(int, stdin.readline().split())
data = list(map(int, stdin.readline().split()))

window = deque()

for i in range(0, n):
    while (len(window) != 0) and (window[-1][1] > data[i]):
        window.pop()
    window.append((i, data[i]))
    if window[0][0] <= i-l:
        window.popleft()
    print(window[0][1], end=" ")

 

결국 책 보고 해결한 문제... 흑흑 플ㄹㅐ 너무 어렵다... (정답)