codeforces 674 round 리뷰
참가후기
코드포스 div3 674 라운드에 참여했습니다
평일 오후 5시에 열렸었는데 다른 일정과 겹쳐서 정신없었던 기억이 나네요
그리고 A번부터 5번이나 틀렸어요
가뜩이나 없던 정신이 파샤샤하고 부서졌지요
대회가 끝난 뒤에 문제들을 천천히 살펴봤더니 생각보다는 쉬웠습니다 (그래서 div 3)
A번 하나를 대회 시간에 풀고, B,C,E는 대회 끝나고 풀었습니다
이 문제들에 대해 리뷰해볼게요
A. Floor Number
문제 링크 : https://codeforces.com/contest/1426/problem/A
문제 설명
Vasya님이 Petya님 집으로 놀러가려고 합니다.
Petya님의 아파트 번호 n(호같은 개념인듯)이랑 각 층마다 몇 개의 호수로 이루어져있는지의 정보(x)로 Petya님 집은 몇층인지 알아맞추는 문제입니다.
단 1층에 항상 2개의 집이 있고, 나머지 층마다 x개의 집이 있습니다.
풀이
n이 1이나 2가 들어오면 무조건 1층을 return 합니다
이외의 값이 들어오면 반복문을 통해서 floor를 구해주는 작업을 해줬습니다
import sys
input = sys.stdin.readline
t = int(input())
for i in range(t):
n,x = map(int,input().split())
floor = 1
if n == 1 or n == 2:
print(floor)
else:
floor= 2
while True:
limit = (floor-1)*x + 2
if limit >= n:
print(floor)
break
else:
floor+=1제가 푼 풀이가 효율적인 풀이는 아닙니다
반복문 없이 수식으로 끝낼 수 있거든요
그러면 시간복잡도가 줄어들겠죠??
B. Symmetric Matrix
문제 링크 : https://codeforces.com/contest/1426/problem/B
문제 설명
이걸 제가 제대로 이해한건지는 모르겠지만 제가 이해한 방식으로 알려드릴게요
n개의 타입을 지닌 2*2 사이즈의 타일이 무한개 있습니다
n이 2라면
1 1
1 1
4 5
6 7
이렇게 생긴 두 타입의 타일이 무한개 있는 겁니다
얘네들을 회전시키지 않고 이어 붙여가면서 m*m 사이즈로 만드려고 해요
겹쳐붙이기는 불가능하고, 모든 타일을 다 사용해야만 하는 것은 아닙니다
그렇게 이어붙였을때 얘네가 대칭이 될 수 있냐는 문제입니다
여기서 말하는 대칭은 다음과 같습니다
왼쪽 위 대각선을 기준으로 오른쪽 아래로 선을 그었을때 위와 아래가 대칭이면 됩니다
(위 797과 아래 797), (위 88과 아래 88) (위 9와 아래 9가)
풀이
일단 m이 홀수면 22의 타일로는 절대 mm 사이즈의 타일을 만들 수 없습니다
이 경우에는 무조건 NO를 출력하면 되겠죠
또한 주어진 타일들을 전부 사용하라는 조건이 없어요
즉 괜찮은 타일이 하나 있다면 그 타일만으로 m*m사이즈를 만들어도 되죠
괜찮은 타일이라 함은 그 자체만으로 조건을 만족하는 대칭의 타일이 됩니다
그림판으로 작업해서 균형이 안맞군요..
저는 위처럼 abcd가 있다면 a와 d는 기준선이 될테고 b와 c가 같은지 판단해서 괜찮은 타일임을 걸러냈습니다
괜찮은 타일이 있었다면 YES를 출력 없었다면 NO를 출력합니다
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
n,m = map(int,input().split())
check = False
for i in range(n):
a,b = map(int,input().split())
c,d = map(int,input().split())
if b == c:
check = True
if check and m % 2==0:
print("YES")
else:
print("NO")C. Increase and Copy
문제 링크 : https://codeforces.com/contest/1426/problem/C
문제 설명
a=[1]인 배열이 있습니다
한 턴(문제에서는 움직임이라고 표현합니다)에 액션 두 가지중 하나를 골라서 수행할 수 있습니다
- 배열에 있는 값중에 하나를 +1 할 수 있습니다
- 배열에 있는 숫자 아무거나 하나 골라서 배열의 맨 끝에 복사합니다
그래서 무엇을 하고 싶은가 하면 최소한의 턴을 소비해서 배열에 있는 모든 숫자의 합 sum(a)가 n 이상이 되게 하고 싶습니다
최소한의 턴을 출력하는 문제였습니다
풀이
일단 배열에 값을 더하고~ 복사하는 행위를 그대로 수행하면 안됩니다
최소한의 움직임으로 n보다 큰 값을 얻으려면 먼저 배열에 있는 값을 최대한 늘립니다(1번 액션)
그 이후에 복사하면 더 큰 값을 얻을 수 있습니다(2번 액션)
그래야 빨리 값에 도달할 수 있어요
저의 경우에는 1번 액션을 n의 제곱근으로 고정했습니다
2번 액션의 경우에는 n의 제곱근을 기준으로 ((n-1))//n의 제곱근-1이 됩니다
따라서 아래의 수식으로 풀었습니다
import sys
import math
input = sys.stdin.readline
t = int(input())
for _ in range(t):
n = int(input())
temp = int(math.sqrt(n))
print(temp+ ((n-1))//temp-1)처음에는 다른 수식으로 풀었는데 그 수식보다 이 수식이 간편해서 Editorial을 참고했습니다
E. Rock, Paper, Scissors
문제 링크 : https://codeforces.com/contest/1426/problem/E
문제 설명
앨리스와 밥이 가위바위보를 합니다
가위바위보의 룰은 익히 알고 계시리라 생각해서 패스하겠습니다
아무튼 n번 가위바위보를 합니다
이때 앨리스와 밥이 가위와 바위와 보를 낸 횟수가 주어집니다
a1은 앨리스가 낸 바위, a2는 가위, a3는 보, b1는 밥이 낸 바위, b2는 가위,b3는 보입니다
앨리스가 최소로 이긴 횟수, 앨리스가 최대로 이긴 횟수를 출력하는 문제였습니다
풀이
min보다는 max를 더 먼저 생각할 수 있을거에요
최대 이긴 값 : min(a1,b2)+min(a2,b3)+min(a3,b1)
앨리스의 바위는 밥의 가위를 이깁니다
즉 앨리스가 이기는 경우들을 계산해준 겁니다
min이 문제인데요
앨리스가 이기지 못한다 = 진다가 아닙니다
앨리스가 이기지 못함 = 앨리스가 지거나 비긴다가 됩니다
저는 이걸 표로 먼저 그리고 손으로 푼 행위를 그대로 코드로 옮겨적었거든요?
뭐라고 표현해야할지 모르겠는데 max와는 달리 min을 구할때는 상쇄시켜주는 작업이 필요해요
상대방의 패를 이길 수 있는 애들을 미리 줄여놓는 작업이죠
앨리스의 가위 - min(앨리스의 가위,밥의 가위+밥의 바위) 이런 식으로요
그렇게 상쇄된 모든 값들을 더하면 min값이 됩니다
import sys
input = sys.stdin.readline
t = int(input())
alice = list(map(int,input().split()))
bob = list(map(int,input().split()))
maxwin = min(alice[0],bob[1]) + min(alice[1],bob[2])+min(alice[2],bob[0])
minlose = (alice[0]-min(alice[0],bob[0]+bob[2])) + (alice[1]-min(alice[1],bob[1]+bob[0])) + (alice[2]-min(alice[2],bob[2]+bob[1]))
print(minlose,maxwin)결론
어려울거라 판단하고 문제도 읽지 않고 도망친 문제가 꽤 있습니다
추석 연휴에 너무 놀기만 해서 해본건데 괜찮았네요
미리 겁을 먹을 필요는 없었는데.. 영어라서 그런가 더 겁 먹었나봐요
아니면 시간 제한이 없어서 여유로운 마음에 괜찮았거나..??
어느 쪽이라도 계속 접해봐야 고쳐질 단점이네요
