Being Programmer

문제 번호 : 16938

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

Code

import itertools


def diff(num):
    return max(num) - min(num)


n, l, r, x = map(int, input().split())
a = list(map(int, input().split()))
count = 0

for i in range(2, n+1):
    numbers = list(itertools.combinations(a, i))
    for number in numbers:
        if l <= sum(number) <= r:
            if diff(number) >= x:
                count += 1

print(count)

Idea

1. N개의 난이도를 2개 이상으로 조합해서 조건에 맞는지 확인한다.
2. combination한 후 list의 요소는 iterable한 튜플 형으로 모든 난이도의 합은 sum 함수로 구현이 가능하다.
3. 차를 구하는 함수는 최대값에서 최소값을 빼주는 형태로 가능했다.
4. 두 조건을 모두 만족하면 count 값을 1씩 증가시키고 마지막에 출력한다.

이전의 문제들보다 난이도가 낮은 편이었다. 처음에는 n이 1인 경우에 print(0)을 먼저 하는 경우를 생각했었는데 print를 2번하게 되어서 채점중(99%)에서 "틀렸습니다"가 나왔다. 아무래도 마지막 입력에서 n이 1인 듯하다. n이 1이면 2개 이상을 조합으로 뽑아올 수 없다.

문제 번호 : 16936

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

Code

import sys


def able(height, width, row, col):
    if row <= height and col <= width:
        if row <= width and col <= height:
            return 3
        else:
            return 1
    elif row <= width and col <= height:
        return 2
    else:
        return 0


h, w = map(int, input().split())
n = int(input())
stickers = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
result = 0

for i in range(len(stickers)):
    r, c = stickers[i][0], stickers[i][1]
    way = able(h, w, r, c)
    if way > 0:
        if way == 1:
            new_hw = [h-r, w, h, w-c]
        elif way==2:
            new_hw = [h-c, w, h, w-r]
        else:
            new_hw = [h-r, w, h, w-c, h-c, w, h, w-r]

        for sticker in stickers[i+1:]:
            new_r, new_c = sticker[0], sticker[1]
            for j in range(0, len(new_hw), 2):
                if able(new_hw[j], new_hw[j+1], new_r, new_c) > 0:
                    result = max(r*c + new_r * new_c, result)
print(result)

Idea

1. 스티커의 한 변의 길이가 모눈종이의 높이보다 작거나 같고 다른 한 변의 길이가 모눈종이의 너비보다 작거나 같으면 스티커를 모눈 종이에 붙일 수 있다.
   단순히 붙일 수 있는지 확인하는 것은 max(r, c) < max(h, w) and min(r, c) < min(h, w) 로 구현하면 된다.
2. 붙일 수 있는 스티커면 일단 붙인다.
   

   

3.  1번 영역에 스티커가 붙어 있으면 2번 영역 + 4번 영역, 3번 영역 + 4번 영역 두 가지 위치에 붙일 수 있다.
   따라서 이 때 새로운 크기를 가진 모눈 종이가 생긴다고 생각한다.
   이 새 모눈 종이들의 높이와 너비를 new_hw 리스트에 저장한다.
4. 현재 붙은 스티커 이후의 스티커들이 새 모눈 종이에 붙일 수 있는지를 판별하고 그 때의 넓이가 더 커지면 result를 갱신한다. 

처음에는 stickers를 넓이를 기준으로 내림차순으로 정렬한 후 두 스티커가 붙게 되면 무조건 최대값이니까 break문을 사용해서 최대한 반복문을 덜 돌게 하려고 노력했고 입력 예제 입력들은 모두 통과가 되는데 코드 제출하니까 "틀렸습니다."라고 나왔다. 

[백준][파이썬] 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] 이된다.

문제 번호 : 16922

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

Code

import itertools

n = int(input())
rome = [1, 5, 10, 50]


comb = list(itertools.combinations_with_replacement(rome, n))
data = set([])
for t in comb:
    data.add(sum(t))

print(len(data))

조합(Combination) 문제라 생각하고 itertools를 사용해서 문제를 풀어봤다. rome이라는 데이터셋에서 n개의 데이터를 반복이 되도록 조합한다. comb 리스트 안에 각 원소들은 tuple 자료형이다. 그냥 조합만을 사용해서 했을 경우에는 합이 중복되는 경우가 존재했고 data라는 집합 자료형에 각 튜플들의 합을 넣어주면서 중복을 피했다.

중복이 일어나는 예시로는 n이 6인 경우 XXXXXV 와 LIIIII 이 둘 다 55의 값을 가지게 된다.

※주의할 점

• combinations_with_replacement()의 반환 형태가 class로 존재하며 이것을 iterable한 자료형으로 바꿔주어야 한다. 
• 집합 자료형은 중복을 허용하지 않고 인덱스를 가지지 않는다.

다음 코드는 itertools를 import하지 않고 반복문을 사용한 코드이다.

n = int(input())
rome = [1, 5, 10, 50]
result = set([0])
for _ in range(n):
    result = set([i + j for i in result for j in rome])

print(len(result))

처음에 n 만큼 반복하면서 result에 원소들을 넣는 것이 아니라 완전히 새로운 집합으로 만든다.

위의 for 문와 비슷하게 다음 코드를 조금 더 보기 쉽게 만든 것이다.

tmp = []
for _ in range(n):
    for i in result:
        for j in rome:
            tmp.append(i + j)
    result = set(tmp)
    tmp = []