A번 Knob(30617)

문제

풀이

t = int(input())

p = 0

lt = []
rt = []

for i in range(t):
    l, r = map(int, input().split())
    
    lt.append(l)
    rt.append(r)

    if i+1 >= 2:
        if lt[i-1] == l and l != 0:
            p += 1
        if rt[i-1] == r and r != 0:
            p += 1
    
    if l == r and l != 0 and r != 0:
        p += 1

print(p)

t를 입력받고 각 loop 마다의 왼쪽 노브, 오른쪽 노브를 기억하기 위해 list lt와 rt를 정의하고, 전체 재미도를 저장하기 위한 변수 p를 정의한다.

각 시도마다 왼쪽 노브, 오른쪽 노브의 조작을 입력받아 각각 l과 r에 저장하고, 만들어둔 lt과 rt에 추가한다.

재미도를 측정하는 방법을 보면, 2번째 박자 또는 그 이후라는 조건이 달려있는 부분이 있으므로 2번째 시도부터 그 lt와 rt에서 이전의 방향을 보고 같은지 판별했고, 노브를 돌리지 않고 가만히 두는 경우는 제외해야한다.

박자와는 상관없이, 같은 방향으로 돌릴 때는 재미도가 증가해야 하므로 이번에도 가만히 두는 경우는 제외하고, 돌릴 때 같은지 판별하여 재미도를 증가시켰다.

그리고, t번의 시도가 끝나면 총합 p를 출력하여 결과를 낸다.

주의해야할 점이 노브를 안 돌릴 때는 재미도를 증가시키지 않는다는 것만 조심하면 쉬운 logic인 것 같다.

B번 Donstructive(30618)

문제

예제 입력 1

4

예제 출력 1

2 3 4 1

풀이 1 (메모리초과)

n = int(input())

l = list(range(1, n+1))
count = [0]*n
result = [0]*n
arr = []

for k in range(n):
    for j in range(n, -1, -1):
        for i in range(k, j):
            arr.append(l[i])

for i in range(len(arr)):
    count[arr[i]-1] += 1

while (True):
    for i in range(len(count)):
        if 0 not in result:
            break
        
        if count[i] == max(count) and max(count) > 0:
            result[i] = max(l)
            count[i] = 0
            for j in range(len(l)):
                if l[j] == max(l) and max(l) > 0:
                    l[j] = 0

    if 0 not in result:
            break

for i in result:
    print(i, end=' ')

이 문제는 문제를 이해하기가 좀 어려워서 시간이 걸렸다. 순열의 정의는 쉽게 이해할 수 있었는데 예제 입력과 예제 출력을 보고 왜 저런 결과가 나오는지 이해하는데 시간이 걸렸다.

나는 당연히 4를 넣으면 [4, 3, 2, 1]으로 나올 줄 알았다. 하지만 직접 연속 부분 수열을 만들어보고 합계를 계산해보고 직접 숫자를 세보면서 깨달았다.
힌트에 있는 연속 부분 수열 예시를 들어보면
2: 4번
3: 6번
4: 6번
1: 4번
이렇게 나온다.
즉, 8 + 18 + 24 + 4 = 54점이 나온다.

그러면, [4, 3, 2, 1]은
[4], [4, 3], [4, 3, 2], [4, 3, 2, 1], [3], [3, 2], [3, 2, 1], [2], [2, 1], [1]
이렇게 연속 부분 수열이 나오고
4: 4번
3: 6번
2: 6번
1: 4번
이렇게 나온다.
즉, 16 + 18 + 12 + 4 = 50점이 나온다.

따라서, 2 3 4 1이 출력이 되는 것이다.

점수를 최대한 높이려면 제일 큰 수는 제일 많이 나와야하고, 제일 작은 수는 제일 적게 나와야 한다는 점이 핵심이다.
즉, 4는 제일 많아야하고, 1은 제일 적어야한다.

그래서, 나는 n를 입력받고 range 함수로 1부터 n까지의 list를 만들었다. 그 다음, 3중 for문으로 연속 부분 수열을 만드는 부분을 구현했다.

만약 n이 4라면
k: 0 1 2 3
j: 4 3 2 1

k=0)
0 1 2 3
0 1 2
0 1
0

k=1)
1 2 3
1 2
1

k=2)
2 3
2

k=3)
3

i가 이렇게 출력될 것이다.
그리고 arr에 append 한다는 것은 각 자리수가 얼마나 많이 나왔냐를 보기 위해서다. 각 자리수의 빈도를 count에 저장했다.
count는 만약 n이 4라면
4 6 6 4의 형태가 될 것이다.

그 다음 반복문을 통해 count에서 제일 큰 index를 result 리스트의 index로 한 후에, l에서 제일 큰 값을 넣고, 해당 l값을 0으로 바꿔주는 작업을 하여 0이 result 리스트에 없다면 반복문을 나가 결과를 출력하도록 했다.
다만, 각 시도에서 l의 가장 큰 값을 0으로 바꿔주는 과정에서, l item이 모두 0으로 바뀌었을 때 한번 loop가 돌아가면 0이 max 값으로 잡혀 result에 들어갈 수 도 있으므로 0을 체크하는 조건식도 포함되어야 했다.

이 코드도 내가 테스트 해본 바로는 정상적으로 출력이 되었다.
하지만, 백준에 돌려보면 메모리 초과 혹은 시간 초과 등의 문제가 있다.
따라서 아래의 코드로 바꿔 제출했다.

풀이 2 (정답)

#b
n = int(input())

for i in range(1, n+1):
    if i%2 == 1:
        print(i, end=' ')

for i in range(n, 0, -1):
    if i%2 == 0:
        print(i, end=' ')

코드 1에서 출력 값을 보면
n=4)
1 3 4 2
n=5)
1 3 5 4 2
n=10)
1 3 5 7 9 10 8 6 4 2

이러한 형태로 나타난다.

그래서 이 수열이 패턴이 있다고 생각해서 그 패턴을 구현하여 코드 2로 제출했다.
이것이 가능한 이유는 점수가 가장 높은 순열이 여러 가지라면 그 중 아무거나 하나를 출력한다는 조건이 있기 때문이다.

패턴을 보면 n의 숫자까지 오름 차순으로 홀수를 출력한 뒤, n 숫자부터 내림차순으로 짝수를 출력한다.

따라서 이러한 형태로 구현하여 풀었다.

C번

C번부터는 풀지 못했다.