1부터 K까지 prime에 해당된 소수를 전부 곱했을 때, 해당 소수(prime)의 지수를 묻는 것과 동일하게 볼 수 있겠다.
이하는 코드가 되겠다.
import math
import sys
from collections import defaultdict
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
N = int(input())
prime = list(map(int,input().split())) #prime의 길이가 N
K = int(input())
answer = 0
for i in range (0,N):
cnt = 0
num = K
while num > 1:
cnt += (num // prime[i])
num //= prime[i]
answer += cnt
print(answer)
import sys
import heapq
input = sys.stdin.readline
N = int(input())
M = int(input())
gp = [[] for _ in range (0,N+1)]
for _ in range (0,M):
a,b,cost = map(int,input().split())
gp[a].append((b,cost))
start, end = map(int,input().split())
INF = int(1e9)
dist = [INF for _ in range (0,N+1)]
q = []
dist[start] = 0
heapq.heappush(q, (dist[start], start))
while q:
distance, node = heapq.heappop(q)
if dist[node] < distance:
continue
for next, next_dist in gp[node]:
d = distance + next_dist
if d < dist[next]:
dist[next] = d
heapq.heappush(q, (dist[next], next))
print(dist[end])
학생의 번호가 1~100 / 추천 횟수가 1000회 이하이므로 100 x 1000을 해도 연산에 있어 어려움은 없을 것 같다.
답안 코드는 다음과 같다.
import sys
from collections import defaultdict
input = sys.stdin.readline
N = int(input()) #사진틀의 개수
m = int(input())
rcd = list(map(int,input().split()))
candidate = defaultdict(int)
date = defaultdict(int)
cnt = 0 #사진틀의 현재 갯수
for i in range (0,m):
#사진첩에 걸린 후보수가 N에 도달했는지 확인
if len(list(candidate.keys())) < N:
candidate[rcd[i]] += 1
if date[rcd[i]] == 0:
date[rcd[i]] = i + 1 #시점 등록
else: #사진첩에 걸린 후보수가 N인 경우
if candidate[rcd[i]] == 0:#날짜 초기화도 해야함
number = list(candidate.keys())
removing = [] #없앨 후보자
min_vote = int(1e9)
for num in number:
if candidate[num] != 0:
min_vote = min(min_vote, candidate[num])
for num in number:
if candidate[num] == min_vote:
removing.append((num, date[num]))
removing.sort(key = lambda x : x[1])
del_candidate, _ = removing[0][0], removing[0][1]
candidate[del_candidate] = 0
candidate[rcd[i]] += 1
date[del_candidate] = 0
date[rcd[i]] = i + 1
else:
candidate[rcd[i]] += 1
number = list(candidate.keys())
answer = []
for num in number:
if candidate[num] != 0:
answer.append(num)
answer.sort()
print(*answer)
N, T, A라는 숫자가 주어지고, A와 T는 각각 현재 득표수를 나타내는 상황이며 N은 총 표수를 나타낸다.
이때 이 선거의 결과 여부를 판단하는 문제가 되겠다.
남아있는 표수를 구한 뒤, 케이스를 나눠 계산해주면 되겠다.
import sys
input = sys.stdin.readline
n,t,a = map(int,input().split())
remain = n - t - a
if t <= a:
if t + remain < a:
print("Yes")
else:
print("No")
elif a <= t :
if a + remain < t:
print("Yes")
else:
print("No")
주어진 문자열을 규칙에 맞게 출력해주면 되겠다.
즉, 아래에서부터 위로 읽어주는건데 (f->d->a... 순), 마지막에 딸려있는 공백은 읽지 않고,
중간에 껴있는 공백은 *를 넣어주면 되겠고, 해당 코드는 아래와 같이 나오겠다.
import sys
input = sys.stdin.readline
N = int(input())
max_length = -1
word = []
for _ in range (0,N):
s = input().rstrip()
word.append(s)
max_length = max(max_length, len(s))
new_word = []
for i in range (0,N):
new_s = word[i] + (max_length - len(word[i])) * "*"
new_word.append(new_s)
answer = []
for i in range (0,max_length):
word = ""
cnt = 0
for j in range (N-1,-1,-1):
if new_word[j][i] != "*":
word += cnt * "*"
word += new_word[j][i]
cnt = 0
else:
cnt += 1
answer.append(word)
for ans in answer:
print(ans)
주어진 쿼리에 따라서 명령어를 수행하면 되겠다.
1은 볼을 넣고,
2는 볼을 빼고, (반드시 있다는 것이 보장)
3은 현재 숫자가 쓰여있는 볼의 종류 갯수 출력
딕셔너리를 사용하면 더욱 간편하게 풀 수 있는 것 같다. (시간복잡도도 굉장히 좋기때문)
import sys
from collections import defaultdict
input = sys.stdin.readline
Q = int(input())
d = defaultdict(int)
cnt = 0
def f(cmd):
global d
global cnt
if len(cmd) == 1: #케이스 3의 경우
print(cnt) #cnt가 갯수를 뜻하겠다
elif len(cmd) == 2:
if cmd[0] == 1: #케이스 1의 경우
d[cmd[1]] += 1
if d[cmd[1]] == 1:
cnt += 1
elif cmd[0] == 2: #케이스 2의 경우
d[cmd[1]] -= 1
if d[cmd[1]] == 0:
cnt -= 1
for _ in range (0,Q):
cmd = list(map(int,input().split()))
f(cmd)
3차원 prefix 문제가 되겠다.
3차원의 직육면체를 분할해서 생각해보면 좋을 것 같다.
import sys
from collections import defaultdict
input = sys.stdin.readline
N = int(input())
num = [[[0 for _ in range (0,N+1)] for _ in range (0,N+1)] for _ in range (0,N+1)]
for i in range (0,N):
for j in range (0,N):
a = list(map(int,input().split()))
for k in range (0,N):
num[i+1][j+1][k+1] = a[k]
prefix = [[[0 for _ in range (0,N+1)] for _ in range (0,N+1)] for _ in range (0,N+1)]
for i in range (1,N+1):
for j in range (1, N+1):
for k in range (1,N+1):
prefix[i][j][k] = prefix[i][j][k-1] + prefix[i][j-1][k] + prefix[i-1][j][k] - prefix[i-1][j-1][k] - prefix[i-1][j][k-1] - prefix[i][j-1][k-1] + prefix[i-1][j-1][k-1] +num[i][j][k]
Q = int(input())
for _ in range (0,Q):
l_x,r_x,l_y,r_y,l_z,r_z = map(int,input().split())
l_x,l_y,l_z = l_x-1, l_y-1, l_z-1
answer = prefix[r_x][r_y][r_z] - prefix[l_x][r_y][r_z] - prefix[r_x][l_y][r_z] - prefix[r_x][r_y][l_z] + prefix[r_x][l_y][l_z] + prefix[l_x][r_y][l_z] + prefix[l_x][l_y][r_z] - prefix[l_x][l_y][l_z]
print(answer)
num_i 부터 num_j까지의 합은 prefix_sum[j] - prefix_sum[i-1] 가 됩니다.
이를 활용하면 다음과 같습니다.
import sys
input = sys.stdin.readline
N,S = map(int,input().split())
num = list(map(int,input().split()))
prefix = [0]
for i in range (0,N):
prefix.append(prefix[-1] + num[i])
answer = []
l,r = 0,1
while l < r and r != N+1:
partial_sum = prefix[r] - prefix[l]
if partial_sum >= S:
answer.append(r-l)
l += 1
elif partial_sum < S:
r += 1
answer.sort()
if len(answer) == 0:
print(0)
else:
print(answer[0])
이제 다음 스텝을 생각한다면 모든 블럭의 높이를 1씩 올린다 했으므로 3 5 4 2가 되겠습니다.
이렇게 해도 변화는 없겠습니다.
이제 높이가 1인 블럭을 어디에 넣느냐? 가 중요해집니다.
1. 가장 왼쪽에 넣을 때
1 3 5 4 2 가 되면서
i = 5, j = 3, k = 3이 되겠습니다. (i, j가 1씩 늘어났습니다.)
2. 가장 오른쪽에 넣을 때
3 5 4 2 1이 되면서
i = 5, j = 2, k = 4가 되겠습니다. (j, k가 1씩 늘어났습니다.)
3. 그 외에 넣을 때
3 1 5 4 2 i = 5, j = 2, k = 3
3 5 1 4 2 i = 5, j = 2, k = 3
3 5 4 1 2 i = 5, j = 2, k = 3 (i만 1이 늘어났습니다.)
그렇다면 이러한 상황을 코드로 작성한다면 다음과 같이 되겠습니다.
import sys
input = sys.stdin.readline
T = int(input())
for _ in range (0,T):
n,l,r = map(int,input().split())
dp = [[[0 for _ in range (0,r+2)] for _ in range (0,l+2)] for _ in range (0,n+2)]
dp[1][1][1]= 1
for i in range (2, n+1):
for j in range (1, l+1):
for k in range (1, r+1):
dp[i][j][k] += dp[i - 1][j - 1][k]
dp[i][j][k] += dp[i - 1][j][k - 1]
dp[i][j][k] += dp[i - 1][j][k] * (i - 2)
print(dp[n][l][r])
