처음에 문제 이해를 잘못했었는데, 차분히 잘 생각해보니까 어느정도 구조가 눈에 보이기 시작했다.
즉, 주어진 "N 이하의 예쁜 수들로" N을 어떻게 만들 수 있을까? 라는 문제가 되겠다.
import math
N, K = map(int,input().split())
pretty_number = []
for i in range (1, N + 1):
str_i = str(i)
n = len(str_i)
summary = 0
for j in range (n):
summary += int(str_i[j])
if i % summary == 0:
pretty_number.append(i)
dp = [0 for _ in range (0, N + 1)]
for i in range (0, len(pretty_number)):
dp[pretty_number[i]] += 1
for j in range (pretty_number[i] + 1, N + 1):
dp[j] += dp[j - pretty_number[i]]
print(dp[-1] % K)
굉장히 그리디하게 풀면 될 것 같은 느낌 (경우의 수를 구하는 경우에서는 특히 브루트포스로 구해도 될 것 같다)
답안 코드는 이하와 같다.
import sys
from collections import defaultdict
input = sys.stdin.readline
N = int(input())
dict = {}
num = {}
for i in range (0,10):
dict[i] = str(i)
num[str(i)] = i
for i in range (0,26):
dict[i + 10] = chr(i + 65)
num[chr(i + 65)] = i + 10
summary = [0 for _ in range (0,36)]
#여기까지 기본 세팅
for _ in range (0,N):
string = input().rstrip()
t = len(string)
for i in range (0,t):
summary[num[string[i]]] += (36 ** (t - i - 1))
K = int(input())
answer = 0
maximize = []
for i in range (0,36):
maximize.append([dict[i], (35 - i) * summary[i]])
maximize.sort(key = lambda x: -x[1])
for i in range (0,K):
answer += 35 * summary[num[maximize[i][0]]]
for i in range (K,36):
answer += num[maximize[i][0]] * summary[num[maximize[i][0]]]
answer_string = []
while answer != 0:
answer_string.append(dict[answer % 36])
answer //= 36
answer_string = answer_string[::-1]
if answer_string != []:
print("".join(s for s in answer_string))
else:
print("0")
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)
