[백준] 1780, 2231 - Python3

2231. 분해합

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

내 풀이 - 성공

from sys import stdin

N = int(stdin.readline())

ans = 0
for n in range(1, N):
    s = str(n)
    M = n
    for c in s:
        M += int(c)
    if M == N:
        ans = n
        break

print(ans)

뭔가 규칙을 찾으려 했지만... 안됐고
브루트포스로 하니까 통과됐다

1 ~ N-1 까지의 숫자들이 N 의 생성자가 되는지 일일이 확인
가장 먼저 발견된 생성자가 가장 작으므로 break

1 ~ N-1 의 범위는 너무 큰 것 같아서 범위를 줄여봤다

• start = N - 자릿수*9 => 실패
• start = N//2 => 통과
  

참고) 분해합을 구하는 다른 방식

s = list(map(int, str(n)))
M = n + sum(s)

---

1780. 종이의 개수

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

내 풀이 - 실패

from sys import stdin
import collections

N = int(stdin.readline())
paper = []
for i in range(N):
    p = list(map(int, stdin.readline().split()))
    paper.append(p)

ans = [0]*3

papers = collections.deque([paper])
while papers:
    p = papers.popleft()
    
    # 종이 p 가 몇가지의 숫자로 이루어져있는지 확인
    nums = []
    for i in range(len(p)):
        for j in range(len(p[i])):
            if p[i][j] not in nums:
                nums.append(p[i][j])
        if len(nums) > 1:
            break
            
    l = len(p)
    a = l//3
    # 여러개의 숫자로 이루어져있는 경우 9 등분
    if len(nums) > 1 and a > 1:
        for i in range(0, l, a):
            for j in range(0, l, a):
                paper = []
                for k in range(3):
                    paper.append(p[j+k][i:i+a])
                if len(paper) > 0:
                    papers.append(paper)
    # 종이의 크기가 3*3 인 경우 => 숫자 하나하나가 종이이므로 세줌
    elif len(nums) > 1 and a == 1:
        for i in range(len(p)):
            for j in range(len(p[i])):
                ans[p[i][j]+1] += 1
    # 종이가 하나의 숫자로 이루어진 경우 ans + 1
    else:
        ans[nums[0]+1] += 1

print(ans)

papers 에 확인해야하는 종이들을 모두 저장해서
하나씩 pop 해가면서 같은 숫자로 이루어졌는지 확인

다른 숫자로 이루어져있다면 9 등분 해서 각 종이마다 papers 에 저장
같은 숫자로 이루어져있다면 해당 값 + 1

다른 사람의 풀이

import sys
input = sys.stdin.readline

n = int(input())
minus_cnt, zero_cnt, plus_cnt = 0, 0, 0

papers = []
for _ in range(n):
    row = list(map(int, input().rsplit()))
    papers.append(row)

def check(row, col, n):
    global minus_cnt, zero_cnt, plus_cnt
    curr = papers[row][col]

    for i in range(row, row + n):
        for j in range(col, col + n):
            if papers[i][j] != curr:
                next_n = n // 3
                check(row, col, next_n)  # 1
                check(row, col + next_n, next_n)  # 2
                check(row, col + (2 * next_n), next_n)  # 3
                check(row + next_n, col, next_n)  # 4
                check(row + next_n, col + next_n, next_n)  # 5
                check(row + next_n, col + (2 * next_n), next_n)  # 6
                check(row + (2 * next_n), col, next_n)  # 7
                check(row + (2 * next_n), col + next_n, next_n)  # 8
                check(row + (2 * next_n), col + (2 * next_n), next_n)  # 9
                return

    if curr == -1:
        minus_cnt += 1
    elif curr == 0:
        zero_cnt += 1
    elif curr == 1:
        plus_cnt += 1
    return

check(0, 0, n)

print(minus_cnt)
print(zero_cnt)
print(plus_cnt)

분할정복 이용 => 재귀함수 check()

주어진 papers[row][col] 와 다른 값이 하나라도 존재하면 9 등분
현재 종이가 모두 같은 값이라면 해당 cnt + 1

분할정복 연습하기!!!