NYPC 문제풀이
개요
NYPC 는 넥슨에서 개최하는 청소년 프로그래밍 대회입니다.
매년 여름방학 시즌에 진행되어 비교적 학업에 지장을 덜 받고 출전해 볼 수
있습니다.
학원생 중 이 대회를 준비하는 친구들이 많아 문제풀이를 지속적으로 업데이트할 계획입니다.
자세한 대회 세부 요강 및 기출문제는 NYPC 홈페이지를 참조하기 바랍니다.
NYPC 2024
[본선1519, 라운드기록 복원하기]
https://nypc.github.io/2024/final_3
현재 48점 🤔
n,k = map(int, input().split(' '))
s = input()
# 첫 i 개의 라운드가 진행되었을 때 팀 점수차로 가능한 값들의 집합.
D = [set() for _ in range(n+1)]
# 마지막에서 i 번째 라운드가 진행되었을 때 팀 점수차로 가능한 값들의 집합.
E = [set() for _ in range(n+1)]
# 0라운드 초기값
D[0].add(0)
E[0].add(k)
E[0].add(-k)
# D[i] 계산, 1라운드부터 진행, ?B?R->RBRR
for i in range(1, n+1):
if s[i-1] == 'R':
V = {1}
elif s[i-1] == 'B':
V = {-1}
else:
V = {1, -1} # ?일때 V는 {1, -1}
for j in D[i-1]:
for v in V:
diff = j+v
# 유효점수 차이 범위 확인
if -k+1 <= diff <= k-1:
D[i].add(diff)
#print(D)
# # E[i] 계산, 마지막 라운드부터 역으로 진행
for i in range(1, n+1):
if s[n-i] == 'R':
V = {1}
elif s[n-i] == 'B':
V = {-1}
else:
V = {1, -1}
for j in E[i-1]:
for v in V:
diff = j-v
if -k+1 <= diff <= k-1:
E[i].add(diff)
#print(E)
result = list(s)
# 현재 점수 차이
diff = 0
# 유실된 라운드 복구
for i in range(n):
if s[i] == '?':
red = diff+1 in D[i+1] and diff+1 in E[n-i-1]
blue = diff-1 in D[i+1] and diff-1 in E[n-i-1]
#print(s[i], red, blue, diff)
if red and not blue:
result[i] = 'R'
diff += 1
elif blue and not red:
result[i] = 'B'
diff -= 1
# 복구 불가능
else:
if n-1 == i and k!=diff:
if diff<0:
result[i] = 'B'
elif diff>0:
result[i] = 'R'
else:
#print(s[i], diff)
if s[i] == 'R':
diff+=1
else:
diff-=1
print(''.join(result))
NYPC 2023
[본선1214, 영국우편번호]
https://nypc.github.io/2023/final_1
우편번호를 공백으로 나누고 앞, 뒤 패턴을 비교하며 입력이 일치하는지 확인.
def isAlpha(c):
if ord(c)>=ord('A') and ord(c)<=ord('Z'):
return True
return False
def isNumber(c):
if ord(c) >= ord('0') and ord(c)<=ord('9'):
return True
return False
def checkPost(s, rule):
p = ''
for c in s:
if isAlpha(c):
p+='A'
elif isNumber(c):
p+='9'
if p in rule:
return True
return False
m = int(input())
front_rule = ('AA9A', 'A9A', 'A9', 'A99', 'AA9', 'AA99')
end_rule = ('9AA',)
for i in range(m):
a, b = input().split(' ')
f = checkPost(a, front_rule)
e = checkPost(b, end_rule)
if f and e:
print('YES')
else:
print('NO')
[예선문제, 인류의 적 모기 퇴치]
https://nypc.github.io/2023/round1_p1
N*N 배열마다 십자가, 대각선방향으로 -m 부터 +m 까지 반복하며 얻은 수를
리스트에 저장하고 가장 큰값을 출력.
n, m = map(int, input().split(' '))
lst = [None for _ in range(n)]
for i in range(n):
temp = list(map(int, input().split(' ')))
lst[i] = temp
mcnt = set()
for i in range(n):
for j in range(n):
# cross
cnt = 0
vs = i-m if i-m>=0 else 0
ve = i+m+1 if i+m+1<n else n
hs = j-m if j-m>=0 else 0
he = j+m+1 if j+m+1<n else n
for r in range(vs, ve):
cnt += lst[r][j]
for c in range(hs, he):
if c!= j:
cnt += lst[i][c]
mcnt.add(cnt)
# diagonal
cnt = 0
for k in range(-m, m+1):
if (i+k>=0 and i+k<n) and (j+k>=0 and j+k<n):
cnt += lst[i+k][j+k]
if (i+k>=0 and i+k<n) and (j-k>=0 and j-k<n):
if k!=0:
cnt += lst[i+k][j-k]
mcnt.add(cnt)
print(max(mcnt))
[예선문제, 메이플 새로운 직업고르기]
https://nypc.github.io/2023/round1_1
입력받은 직업을 배열에 저장한 후 키워본 직업을 입력받아 리스트에서 제거.
n = int(input())
jobList = []
for _ in range(n):
job = input()
jobList.append(job)
k = int(input())
for _ in range(k):
job = input()
if job in jobList:
jobList.remove(job)
print(len(jobList))
for job in jobList:
print(job)
[예선문제, 게임 안에서 책을 읽을 수 있다구요?]
https://nypc.github.io/2023/round1_2
입력받은 한줄을 공백을 기준으로 나누고 각 단어들의 시작인덱스와 끝 인덱스를 정리.
단어들의 끝 인덱스가 문서의 폭보다 작은 경우 앞단어의 시작과 끝을 연결시켜
나가며 처리.
def parsingLine(line):
words_idx = []
if len(line.split(' '))==1:
words_idx.append((0, len(line)-1))
else:
k=0
for i in range(len(line)):
if line[i]==' ':
words_idx.append((k, i-1))
k=i+1
words_idx.append((k, len(line)-1))
#print(words_idx)
new_idx = []
s = 0
e = 0
k = 0
for i, v in enumerate(words_idx):
if v[1]-v[0]+k+1<=m:
e = v[1]
k += v[1]-v[0]+1
else:
new_idx.append( (s, e) )
s = v[0]
e = v[1]
k = e-s+1
k+=1
new_idx.append( (s, e) )
#print(new_idx)
return new_idx
def noTag(line):
new_idx = parsingLine(line)
new_line=''
for s, e in new_idx:
word = line[s:e+1].replace(' ', '-')
k = m-len(word)
if k==0:
new_line += word
else:
while len(word)<m:
word += '-'
new_line += word
new_line += '\n'
return new_line[:-1]
def centerTag(line):
new_idx = parsingLine(line)
new_line=''
for s, e in new_idx:
word = line[s:e+1].replace(' ', '-')
k = m-len(word)
if k==0:
new_line += word
elif k==1:
new_line += word+'-'
else:
new_line += '-'*(k//2) + word + '-'*(k//2)
if k%2==1:
new_line += '-'
new_line += '\n'
return new_line[:-1]
def rightTag(line):
new_idx = parsingLine(line)
new_line=''
for s, e in new_idx:
word = line[s:e+1].replace(' ', '-')
k = m-len(word)
if k==0:
new_line += word
else:
while len(word)<m:
word = '-'+word
new_line += word
new_line += '\n'
return new_line[:-1]
def getAlignText(line, tag=0):
#tag 0:none, 1:center, 2:right
if line=='<CENTER>':
return '', 1
elif line=='<RIGHT>':
tag = 2
return '', 2
elif line=='</CENTER>' or line=='</RIGHT>':
return '', 0
else:
if tag==0:
return noTag(line), tag
elif tag==1:
return centerTag(line), tag
else:
return rightTag(line), tag
n,m = map(int, input().split(' '))
lines = []
for _ in range(n):
s = input()
lines.append(s)
tag = 0
for line in lines:
newLine, tag = getAlignText(line, tag)
if newLine:
print(newLine)
NYPC 2022
[본선문제, 조약돌 순서]
https://nypc.github.io/2022/final_1
반복의 횟수를 줄여야 하고 Python의 경우 List 자료형으로 인덱스 접근, deque 자료형으로 Rotation을 처리해서 시간제한을 돌파.
import sys
from collections import deque
s = sys.stdin.readline().rstrip()
k, n = map(int, s.split(' '))
if n==0:
for i in range(k):
sys.stdout.write(f'{i+1} ')
else:
x = deque([str(i+1) for i in range(k)])
z = n//(k-1)%k
for i in range(z):
x.rotate(-1)
z = n%(k-1)
x = list(x)
for i in range(z):
temp = x[i]
x[i] = x[i+1]
x[i+1] = temp
for c in x:
sys.stdout.write(c+' ')
print()
NYPC 2018
[예선문제, 아이템구매]
https://nypc.github.io/2018/2018_online_3.html
부정방정식을 푸는 문제
# y에 대한 방정식
# 1. ax + by = c
# 2. by = c-ax
# 3. y = (c-ax)/b
p, q, w = map(int, input().split(' '))
i=1
while i*p <= w:
if (w-(i*p)) % q == 0:
print(i, (w-(i*p))//q)
break
i+=1
[예선문제, 승리팀찾기]
https://nypc.github.io/2018/2018_online_4.html
아이템전은 가장 빠른 시간을 찾아 그 팀을 출력하고 스피드전은 정렬 후 등수점수를 팀별로 합산.
def itemWinner(records):
best = records[0][1]
idx = 0
for i in range(8):
if best > records[i][1]:
best = records[i][1]
idx = i
return records[idx][0]
def speedWinner(records):
# sort
for i in range(8-1):
for j in range(i+1, 8):
if records[i][1]>records[j][1]:
temp = records[i]
records[i] = records[j]
records[j] = temp
best = records[0][1]
red_score = 0
blue_score = 0
score = (10, 8, 6, 5, 4, 3, 2, 1)
for i in range(8):
if records[i][1]-best<10:
if records[i][0]=='red':
red_score += score[i]
else:
blue_score += score[i]
if red_score>blue_score:
return 'red'
elif blue_score>red_score:
return 'blue'
else:
return records[0][0]
#input
n = int(input())
for _ in range(n):
k = input()
records = []
for _ in range(8):
t, r = input().split(' ')
minu, sec = map(float, r.split(':'))
records.append((t, minu*60+sec))
if k=='item':
print(itemWinner(records))
else:
print(speedWinner(records))
[예선문제, 줄임말]
https://nypc.github.io/2018/2018_online_5.html
파이썬으로 풀면 쉬운문제. 공백을 기준으로 문장을 잘라내서 UTF-8로
저장.
n = int(input())
try:
f = open('ouput.txt', mode='w', encoding='utf-8')
except Exception as e:
print(e)
else:
for i in range(n):
lst = input().split(' ')
for word in lst:
f.write(word[0])
if i!=n-1:
f.write('\n')
f.close()
[예선문제, 우물왕 김배찌]
https://nypc.github.io/2018/2018_online_6.html
분산을 최소화하는 대표값은 평균.
n = int(input())
xp = 0
yp = 0
for _ in range(n):
x, y = map(int, input().split(' '))
xp+=x
yp+=y
print(xp/n, yp/n)
[예선문제, 최고의 동접구간을 찾아라]
https://nypc.github.io/2018/2018_online_7.html
예제 입력은 다 해결했는데 BIKO 제출시 틀렸다는데 반례를 모르겠다. 일단은 여기까지..
def hourToMin(hour):
h, m = map(int, hour.split(':'))
return h*60 + m
def minToHour(min):
h = min//60
m = min%60
return f'{h:02}:{m:02}'
n = int(input())
records = []
for i in range(n):
login, logout = input().split(' ')
records.append( (hourToMin(login), True) )
records.append( (hourToMin(logout), False) )
# sort
records.sort(key=lambda x: x[0])
from collections import defaultdict
counts = defaultdict(set)
for num, flag in records:
counts[num].add(flag)
# 중복되는 항목을 확인
to_remove = {num for num, flags in counts.items() if len(flags) > 1}
# 중복되는 항목을 제거한 새로운 리스트 생성
records = [item for item in records if item[0] not in to_remove]
#print(records)
# find segmemt
user = 0
max_user = 0
max_seg = 0
start_time = 0
k = len(records)
for i in range(k):
isIn = records[i][1]
if isIn:
user +=1
else:
user -=1
if user>max_user:
start_time = records[i][0]
max_user = user
max_seg = i
#print(user)
print(max_user)
print(minToHour(start_time), end=' ')
for i in range(max_seg+1, k):
if records[i][1]==False:
print(minToHour(records[i][0]))
break
지속적으로 업데이트 예정입니다.
댓글
댓글 쓰기