[24.02.20] CF Round 927 div. 3 virtual + Gold 한 문제 풀기

 

A번은 가시가 두 번 나오기 전까지 coin 개수를 더해주면 된다.

import sys
input = sys.stdin.readline
 
T = int(input())
 
for _ in range(T):
    N = int(input())
    st = input().rstrip()
    cnt, flg = 0, 1
 
    for i in range(N-1):
        if st[i] == '@':
            cnt += 1
        if st[i] == '*' and st[i+1] == '*':
            flg = 0
            break
 
    print(cnt+1 if flg and st[-1] == '@' else cnt)

 

B번은 뇌 덜 깸 이슈로 문제 이해하는데 시간이 좀 걸렸다. 나는 처음에 어떤 기준으로 K th 기다림이 성립하는지 이해를 못해서 이것 저것 많이 해봤는데, arr 안에서 arr[0] ~ arr 끝까지 갈 때 무조건 한 번은 arr[k]의 배수 형태로 기다려줘야 한다는 사실을 늦게 발견했다.

그래서 B번은 쉬울 줄 알고 나이브하게 짰는데 TLE 맞길래, 오 B번부터 이분 탐색을 쓰는 건가? 흥미롭군...... 이러면서 이분 탐색을 넣었다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int T;

int upper_bound(int now, int target) {
    int left = 1;
    int right = now/target + 1; // 초기 범위 설정

    while (left < right) {
        int mid = left + (right - left)/2;
        if (mid * target <= now) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> T;

    for (int t = 0; t < T; t++) {
        int N;
        cin >> N;

        vector<int> arr(N);
        for (int i = 0; i < N; i++) {
            cin >> arr[i];
        }

        int now = arr[0];

        for (int i = 1; i < N; i++) {
            if (now >= arr[i]) {
                int cnt = upper_bound(now, arr[i]);
                now = cnt * arr[i];
            } else {
                now = arr[i];
            }
        }
        cout << now << "\n";
    }

    return 0;
}

 

C번은 재밌는 문제였다. 모듈로 연산의 특징을 잘 이용하면 된다. 그런데 문제에서 하라는 대로 Left와 Right를 순서대로 빼서 연산하려고 하면 귀찮아진다. 모듈로 나눗셈을 해야하기 때문이다.

그래서 나는 생각의 전환을 해봤다. 문제에서는 L/R 명령을 기준으로 deque에서 앞/뒤로 빼는 순서를 정해주는데,  이 순서를 그대로 빼서 stack에 저장했다. 이렇게 되면 elements 가 기존 명령 순서와 반대로 스택에 쌓인다. 그 후에 스택에서 값을 하나씩 빼주면서 모듈로 곱셈을 해주고, 각 step 마다의 곱셈 결과를 result list에 저장해주면 된다.

마지막에는 list 순서를 reverse 해서 출력하면 쉽게 답을 구할 수 있다.

import sys
input = sys.stdin.readline

T = int(input())

from collections import deque

for _ in range(T):
    N, M = map(int, input().split())
    arr = list(map(int, input().split()))
    st = list(input().rstrip())

    now = 1
    new = deque()
    for i in range(N):
        new.append(arr[i]%M)
    order = []

    for i in range(N):
        if st[i] == 'L':
            order.append(new.popleft())
        else:
            order.append(new.pop())

    res_arr = []
    res = order.pop() #last element of order stack
    res_arr.append(res)

    for i in range(len(order)):
        tmp = order.pop()
        res = (res*tmp)%M
        res_arr.append(res)

    res_arr.reverse()
    print(*res_arr)

 

D번은... 처음에 게임이라고 하길래 게임 이론 문제인가 싶었다. 난 왜 게임 이론이 무섭지..? 주변에 게임 이론 문제를 좋아하셔서 한동안 이거 태그 달린 문제만 푸시는 분이 있었는데 진심으로 존경한다... (난 아직도 매 회차마다 본인이 이길 수 있는 최선의 선택을 하는게 뭔지 감이 잘 안온다. 공부 할 내용에 추가해야겠다.) 

아무튼 앞 내용은 그냥 헛소리였고 이 문제는 게임 이론과 상관 없는 문제다... 차근차근 다시 읽어 보면 조건 대로 맞춰서 구현해주면 된다. 대신 구현이 조금 시간이 걸려서 이쁘고 깔끔하게 구현하는게 중요하다.

 

E번은 각 자릿수가 바뀔 때마다 1초 추가를 해주면 된다. 대신 한 번에 여러 자리 수가 바뀌게 되면 그것도 다 추가해줘야 해서 약간 성가신 구현이 된다. reverse 해서 카운트 해줬다.

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    N = int(input())
    s = input().rstrip()
    s = s[::-1]

    cnt = [0]*(N+1)
    now = 0

    for num in s:
        now += int(num)

    for i in range(N):
        cnt[i+1] = now
        now -= int(s[i])

    res = []
    for i in range(1, N):
        tmp = cnt[i] % 10
        cnt[i+1] += cnt[i] // 10
        res.append(tmp)

    res.append(cnt[N])
    res = res[::-1] #reverse
    flg = 1
    
    for num in res:
        if flg and num == 0:
            continue
        if num != 0:
            flg = 0
        print(num, end="")
    print()

 

---

 

아침에 일어나서 간단하게 밥먹고 8시 쯤에 버추얼을 돌렸다. 원래 목표는 가볍게 4솔 하고 끝내는거 였는데 B에서 시간을 너무 오래 써버렸다.

전에는 잘 안 와닿았는데 standings를 유심히 보다보니 스피드가 굉장히 중요한 것 같다. 물론 덜 틀려서 패널티 관리하는 것도 중요하지만, 대체적으로 같은 solve 안에서 시간 차로 퍼포가 엄청 갈리기 때문에 쉬운 문제를 빨리 처리하는게 중요하다고 느껴졌다. 물론 쉬운 문제를 빨리 푸는 건 연습 밖에 답이 없다.

나는 대체적으로 풀이를 완성하지 않고 일단 시작하는 편인데, 코드 작성 중에 생각을 수정하면 그대로 시간 소모를 하게 된다. 그래서 쉬운 문제는 풀이를 완결해놓고 들어가는 게 좋을 것 같다. 물론 A번은 그냥 냅다 짜도 잘 맞기 때문에 지금까지 신경 써 본적이 없는데 B번부터는 완결하는 연습을 해야겠다.

 

---

 

오늘 골드 문제는 문자열 관련 문제로 풀어봐야겠다. 어제 배웠던 라빈 카프를 구현해보고 관련 문제를 볼 생각이다... << 풀려고 했는데 chorus 문제가 단순 라빈 카프 적용하는거 뿐만 아니라 후렴구 처리를 한 번 더 해줘야 했다. 후렴구는 반복되는 문자열 중에 가장 긴 부분 문자열이라던데, 이걸 구하는 문제가 또 따로 있어서 이전 step의 문제를 먼저 보고 chorus를 풀 생각이다.

대신에 dp 문제를 하나 풀었다.

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

1915번: 가장 큰 정사각형

 

2차원 격자가 주어져있어서 누가봐도 2차원 dp라는 느낌이 났다. 특히, 이런 문제는 본인을 정사각형의 우측 하단 꼭짓점으로 생각하는 경우가 많아서 그걸 첫 접근으로 시도했다.

우선 한 변이 2인 정사각형은 본인 위치 (i, j) 를 포함한 주변 (i-1, j-1) (i, j-1) (i-1, j)이 모두 1일 때 가능하다. 그러면 이걸 sub-problem 이라고 생각했을 때, 이 정보를 어떻게 저장해서 넘기면 다음 계산을 편하게 만들 수 있을까? 이런 방식으로 생각했다.

정사각형을 여러 모양으로 생각해보다가, 우측 하단 꼭짓점에 현재까지 가능한 변의 길이를 업데이트 하면,  (i, j) (i-1, j-1) (i, j-1) (i-1, j) 이렇게 네 값만 봐도 편하게 알 수 있다는 것을 발견했다.

네 개 중에 단 하나만 0이면 정사각형이 성립하지 않고, 나머지 길이가 다 2로 저장되어 있는데 하나만 1이어도 다음 크기의 정사각형을 만들 수 없었다. 그래서 본인이 만약에 0이 아닌 값을 들고 있다면 (i, j) 4개 칸의 min 값을 봐주고, min + 1 하면 된다.

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
arr = []
for _ in range(N):
    li = list(input().rstrip())
    arr.append(li)

dp = [[0]*M for _ in range(N)]

# 자기 대각선 위 dp[i-1][j-1] 이 정사각형이고,
# 자기까지의 각 row, column이 1이면 ok
# 뭔가 dp[i][j]를 정사각형의 아래 꼭짓점으로 두고 check할 방법?

for i in range(N):
    for j in range(M):
        if arr[i][j] == '1':
            dp[i][j] = 1

for i in range(N):
    for j in range(M):
        if i == 0 or j == 0:
            continue
        if min(dp[i][j], dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) != 0:
            dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])+1

res = 0
for i in range(N):
    for j in range(M):
        res = max(res, dp[i][j])
print(res**2)