AtCoder Beginner Contest 289 정리

출처 : https://atcoder.jp/contests/abc289

Ｓｋｙ Inc, Programming Contest 2023（AtCoder Beginner Contest 289） - AtCoder

 

 

A - flip

가볍게 넘어간다.

import sys
input = sys.stdin.readline
n = input().rstrip()
s = ""
for i in n:
    if i == '1':
        s += '0'
    else:
        s += '1'
print(s)

 

 

 

 

B - V

이 문제도 가볍게 넘어갔어야 하는 문제인데 문제 이해를 잘못해서 애먹었다. 결과적으로 V가 있는 정수끼리는 연쇄되어 있다. 그래서 V가 없다면(연쇄되어 있지 않다면) 연쇄되어 있는 수를 꺼내서 append해주어야 한다.

 

1 V 2 3 V 4 V 5 

 

1과 2는 연쇄, 3, 4, 5는 연쇄되어 있다. 

1. 1을 배열에 넣는다. 

2. V가 존재한다면 continue

3. 2를 배열에 넣는다. V가 존재하지 않는다. 

4. 배열.pop()을 수행 후 정답을 출력할 배열에 넣어준다. -> ans = [2, 1] 순으로 추가된다.

.....

결과적으로 ans = [2, 1, 5, 4, 3]이 된다.

N, M = map(int,input().split())
A = set(map(int,input().split()))

ans, l = [], []
for i in range(1, N+1):
    l.append(i)
    if i in A:
        continue
    else:
        while l:
            ans.append(l.pop())

print(*ans)

 

 

 

 

C - Coverage

주어진 수의 조합을 활용해 1 <= x <= N 이 되는 경우의 수를 모두 출력하면 된다. 즉, 수를 조합하여 1부터 N까지의 수가 모두 포함되어 있느냐를 계산해주어야 한다.

import sys
from itertools import combinations
input = sys.stdin.readline
n, m = map(int, input().split())
compareArr = [i for i in range(1, n+1)]
arr = []
for _ in range(m):
    c = int(input())
    arr.append(list(map(int, input().split())))
ans = 0

sets = []
for i in range(1, len(arr) + 1):
    sets += list(combinations(arr, i))

for i in sets:
    tmp = set()
    for j in i:
        for k in j:
            tmp.add(k)
    tmp = sorted(tmp)

    if compareArr == tmp:
        ans += 1

print(ans)

 

 

 

 

D - Step Up Robot

풀릴 듯 풀릴 듯.......결국 못 푼 문제다. 처음에 접근한 방식은 백트래킹이다. 주어진 배열의 수를 활용해 도달하고자 하는 높이의 계단에 도착할 수 있다면 Yes, 아니면 No를 출력해주는 방식이다.

 

틀린 풀이 => 3개 TLE, 5개 RE 

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
M = int(input())
B = list(map(int, input().split()))
B = set(sorted(B, reverse=True))
target = int(input())
visit = [False for _ in range(target+1)]


def backTracking(count):
    if count == target:
        print("Yes")
        exit(0)

    for num in A:
        nextStep = num + count
        if nextStep > target:
            return

        if not visit[nextStep]:
            if (nextStep) not in B:
                visit[nextStep] = True
                backTracking(nextStep)
                visit[nextStep] = False


visit[0] = True
backTracking(0)
print("No")

 

 

 

1. 배열

다른 사람들의 풀이를 보고 두 가지 방식으로 풀 수 있었다. 두 가지 방법? 이라기 보단 미리 전처리를 해두고 넉넉하게 돌리느냐 이전 상태를 저장하고 간결하게 푸느냐..? 뭐 사실 큰 차이는 모르겠다. trap배열을 set으로 처리해준거? 

 

10**6 배열을 초기화(주어지는 배열 A의 상한이 10^5기 때문에 넉넉잡아 둠) 해주고 시작 위치 start[0] = 1로 둔다. 그리고 주어진 계단 수만큼 이동하는데, trap이 없는 위치일 경우에만 이동한다. 이런 식으로 <= x의 위치만큼 돈다. 

n = int(input())
A = list(map(int, input().split()))
m = int(input())
B = set(map(int, input().split()))
x = int(input())

stair = [0 for _ in range(10**6)]
stair[0] = 1
idx = 0

while idx <= x:
    if stair[idx] == 1:
        for a in A:
            if idx + a not in B:
                stair[idx + a] = 1

    idx += 1

if stair[x] == 1: print("Yes")
else: print("No")

 

 

2. dp 

초기 선언한 배열의 크기만 작을 뿐 방식은 동일하다. 

N = int(input())
A = list(map(int, input().split()))
M = int(input())
B = list(map(int, input().split()))
x = int(input())
dp = [0 for _ in range(x+1)]

for i in B:
    dp[i] = -1
dp[0] = 1

for i in range(x+1):
    if dp[i] == 1:
        for j in A:
            if i+j <= x and dp[i+j] != -1:
                dp[i+j] = 1

if dp[x] == 1:
    print("Yes")
else:
    print("No")

 

내가 풀 수 있는 문제는 D번까지이다. 더 수련해서 E번도 건드려보는 그 날까지....... 화이팅