[백준] 색종이 만들기, [백준] 1학년, [백준] 동전1

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

2630번: 색종이 만들기

재귀

- 재귀를 사용하여 범위를 좁혀가며 whites, blues 계산

import sys

def solution(n, paper):
    def f(i,j,n):
        if n == 1:
            return (1,0) if paper[i][j] == 0 else (0,1)
        
        splits = [f(i,j, n//2), f(i+n//2, j, n//2), f(i,j+n//2,n//2), f(i+n//2,j+n//2,n//2)]
        # print(splits)
        whites = sum(s[0] for s in splits)
        blues = sum(s[1] for s in splits)
        
        if whites == 0:
            return (0,1)
        elif blues == 0:
            return (1,0)
        return (whites, blues)
    return f(0,0,n)
n = int(sys.stdin.readline())
paper = [[*map(int, row.split())] for row in sys.stdin.readlines()]
print(*solution(n,paper), sep='\n')

 

 

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

5557번: 1학년

DP

- counter를 사용해 +,- 해서 나온 수를 count

import sys
from collections import Counter

def solution(N, nums):
    dp = Counter({nums[0]:1})
    
    for num in nums[1:-1]:
        new_dp = Counter()
        for k, cnt in dp.items():
            if k+num <= 20:
                new_dp[k+num] += cnt
            if k-num >=0:
                new_dp[k-num] += cnt
        # print(new_dp)
        dp = new_dp
    return dp[nums[-1]]
N = int(sys.stdin.readline())
nums = [*map(int, sys.stdin.readline().split())]

print(solution(N,nums))

 

 

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

2293번: 동전 1

DP

if k=10 일때 5원을 사용하는 경우와 사용하지 않는 경우가 있다.

사용하는 경우 -> 1,2,5를 사용해 10-5를 만듬

사용하지 X -> 1,2 사용해 10을 만듬

--> f(n, k-coin) + f(n-1, k)

 

import sys

def solution(n,k,coins):
    dp = [1] + [0]*k
    
    for c in coins:
        for money in range(c, k+1):
            dp[money] += dp[money-c]
    return dp[-1]

n,k = map(int,sys.stdin.readline().split())
coins = [*map(int, sys.stdin.readlines())]

print(solution(n,k,coins))