[백준][파이썬] 16936번 - 나3곱2

문제 번호 : 16936

문제 출처 : https://www.acmicpc.net/problem/16936

Code

n = int(input())
B = list(map(int, input().split()))
x = min(B)
old_power = 0

for b in B:
    i = 3
    power = 0
    while i <= b:
        if b % i == 0:
            power += 1
        i *= 3
    if power > old_power or (power == old_power and b < x):
        x = b
        old_power = power
        
A = []
A.append(x)
count = 1
while count < n:
    if x * 2 in B:
        x = x * 2
        A.append(x)
        count += 1
    else:
        x = x // 3
        A.append(x)
        count += 1

for a in A:
    print(a, end=' ')

Idea

1. 가장 큰 수가 짝수이면 얘는 절대 x는 아니다?    False
   
   • 예제 2번에서 보듯 가장 큰 수가 짝수여도 x일 수 있다.
2. 오른쪽으로 갈수록 수의 2^n배 증가하고 3^-n배로 감소한다.
3. 3의 n승을 약수로 가질 때 n이 클수록 왼쪽에 위치한다.
4. 같은 지수를 가지는 수 중에서 가장 작은 수가 x가 된다.
5. x를 시작으로 법칙대로 수를 A 리스트에 삽입한다.

처음에 생각할 때에는 한 노드에서 2 가지를 모두 탐색한 후 다시 되돌아와서 다른 방향으로 가야 될거라 생각했다.

다른 사람들의 풀이에는 재귀함수를 사용한 경우도 많아 보였다. 나는 x를 찾은 후 문제의 알고리즘대로 A 수열을 만들었는데 다른 사람의 코드에서는 이차원 리스트와 lambda를 사용해서 정렬을 하기도 했다.

n = int(input())
b = list(map(int, input().split()))

a = []

for num in b:
    can3 = 0
    num_origin = num
    while True:
        if num % 3 == 0:
            can3 += 1
            num //= 3
        else:
            break
    a.append([can3, num_origin])

a.sort(key= lambda x: (-x[0], x[1]))
for i in range(n):
    print(a[i][1], end=' ')

이 코드가 훨씬 간결해보인다. key = lambda x: (-x[0], x[1])로 정렬한 것은 -x[0] 즉 3으로 나누어지는 수가 큰 것으로 정렬한 후 원래 값이 작은 순으로 정렬한다. 정렬의 기본 순서는 오름차순이므로 -x[0]를 기준으로 하면 큰 수가 앞으로 온다.

반복문을 진행하면서 모든 과정을 끝내는 것을 연습해야 된다고 생각이 들었다.

[백준][파이썬] 16924번 - 십자가 찾기

문제 번호 : 16924

문제 출처 : https://www.acmicpc.net/problem/16924

Code

import sys

n, m = map(int, input().split())
board = [list(sys.stdin.readline().strip()) for _ in range(n)]
answer =[]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

if board[0][0] == '*' or board[0][m-1] == '*' or board[n-1][0] == '*' or board[n-1][m-1]=='*':
    print(-1)
    # 각 모서리에 * 이 있으면 십자가는 찾을 수 있어도 십자가로 그 별을 커버하지 못한다.
else:
    for i in range(1, n-1):
        for j in range(1, m-1):
            if board[i][j] == '*':
                max_size = min(i, j, n-i-1, m-j-1)
                # 십자가의 최대 크기는 상하좌우의 공백길이의 최소값
                for k in range(1, 1 + max_size):
                    count = 0
                    for idx in range(4):
                        nx = i + k * dx[idx]
                        ny = j + k * dy[idx]
                        if board[nx][ny] != '*':
                            break
                        else: count += 1
                    if count == 4:
                        answer.append((i, j, k))
                    else:
                        break
    # board에서 찾은 십자가 위치를 모두 . 으로 바꾼다.
    for pos in range(len(answer)):
        row = answer[pos][0]
        col = answer[pos][1]
        board[row][col] = '.'
        for idx in range(4):
            nr = row + dx[idx] * answer[pos][2]
            nc = col + dy[idx] * answer[pos][2]
            board[nr][nc] = '.'
    # sum(board, [])를 하면 1차원 배열로 바뀌고 그 안 * 이 있는지 찾는다.
    if '*' not in sum(board, []) and len(answer) != 0:
        print(len(answer))
        for ans in answer:
            print(ans[0] + 1, ans[1] + 1, ans[2])
    else:
        print(-1)

Idea

1. 각 모서리에 * 이 있으면 십자가만으로 해당 격자판을 만들 수 없다.
2. 문제에서는 시작을 (1, 1)로 규정했지만 코드를 짤 때는 (0, 0) 에서 시작하는 것으로 한다.
3. 십자가를 찾을 때 최대 크기는 (i, j) 에서 상하좌우 공백 중 가장 짧은 것을 기준으로 한다.
4. size가 1인 십자가가 아닌 경우에는 더 큰 size의 십자가는 만들어 질 수 없다.
5. 찾은 십자가로 격자판을 만들 수 있는가는 두 가지 방법으로 할 수 있다.
   1. 같은 크기의 새로운 배열을 만들어 십자가를 찾을 때마다 해당 위치의 배열 값을 바꾸어준다.
   2. 찾은 십자가 위치를 모두 *이 아닌 다른 문자(여기서는 . )로 바꾸어주고 마지막에 * 이 존재하는지 확인한다.
6. sum(이차원 리스트, []) 를 하게 되면 일차원 리스트로 변환되어서 in 연산자를 사용하기 편해진다.

      ex) li1 = [[1, 2], [2, 4], [4, 8]] 인 경우에 li2 = sum(li1, [])를 하게 되면

           li2 = [1, 2, 2, 4, 4, 8] 이된다.

[백준][파이썬]** 16917번 - 양념 반 후라이드 반

문제 번호 : 16917
문제 출처 : https://www.acmicpc.net/problem/16917

Code

a, b, c, x, y = map(int, input().split())

result = a * x + b * y

if a + b > 2 * c:
    more = a if x >= y else b   # more : 더 많이 시켜야하는 치킨 종류의 가격
    if c * 2 < more:
        result = c * 2 * max(x, y)
    else:
        result = c * 2 * min(x, y) + more * (max(x,y) - min(x,y))
print(result)

Idea

1. 초기 결과 값은 후라이드와 양념을 모두 따로 시키는 방법으로 설정
2. 반반 두 마리를 시켜서 후라이드 한 마리, 양념 한 마리를 만드는 방식이 더 싼 경우를 고려
3. 더 많이 시켜야 하는 치킨 종류의 가격이 반반의 가격보다 비싸면 모두 반반으로 구매
4. 그렇지 않은 경우 더 적은 갯수 까지는 반반으로 시키고 이후에는 한 마리 씩 구매

[백준][파이썬]** 16968번 - 차량 번호판 1

문제 번호 : 16968
문제 출처 : https://www.acmicpc.net/problem/16968

Code

s = input()

if s[0] == 'd':
    result = 10
    state = 1
else:
    result = 26
    state = 0

for ch in s[1:]:
    if ch == 'd':
        result *= (10 - state)
        state = 1
    else:
        result *= (26 + state -1)
        state = 0

print(result)

Idea

1. 입력을 받을 때 문자를 그대로 사용하기 위해서 따로 list형으로 변환하지 않음
2. 입력의 첫 번째 문자가 d인지 c인지에 따라서 state라는 flag를 설정
3. 두 번째 문자부터 확인하면서 상황에 맞게 가능한 갯수를 계산하여 곱 연산
4. 상황에 맞게 state도 변경시켜준다.