BAEKJOON : 1094, 11047, 1003, 14891

No. 1094

1. Problem

2. My Solution

• 비트마스킹을 이용해서 문제 풀이
• 1~64 까지의 자연수는 [1,2,4,8,16,32,64] 의 조합으로 만들 수 있음

X = int(sys.stdin.readline())
poles = [1,2,4,8,16,32,64]

for bit in range(1, 2**7):

    sum = 0
    count = 0

    for i in range(7):
        if bit & (1 << i):
            sum += poles[i]
            count += 1

    if sum == X:   
        print(count)
        break

3. Learned

• 문제 해결 방법이 떠오르지 않는다면, 일단 문제의 답이되는 규칙을 나열해보자

---

No. 11047

1. Problem

2. My Solution

• 그리디 알고리즘 이용 (가격이 높은 동전을 최대한 많이 사용해야함)
• 나눗셈, 나머지 연산을 이용하지 않고 계속해서 뺄셈 연산을 수행하는 것도 가능하지만 N = [1] 이고 K = 100,000,000 이면 총 1억번 연산 수행 -> 시간초과

import sys

n,k = map(int,sys.stdin.readline().rstrip().split())
coins = []
target = k
count = 0

for _ in range(n):
    coins.append(int(sys.stdin.readline()))

coins.sort(reverse=True)

for i in coins:

    if target == 0:
        break
    elif i == 1:
        count += target
        break
    elif target / i >= 1:
        count += target // i
        target = target % i

print(count)

---

No. 1003

1. Problem

2. My Solution

• 첫 번째 방법
• Top Down DP 를 직접 돌려가면서 count -> 시간초과

import sys

def fib(n):
    if n == 0 :
        result[0] += 1
        return 0
    elif n == 1:
        result[1] += 1
        return 1
    elif dp[n] != -1:
        return dp[n]
    else:
        return fib(n-1) + fib(n-2)
        
test_n = int(sys.stdin.readline())

for _ in range(test_n):
    n = int(sys.stdin.readline())
    result = [0,0]
    dp = [-1] * 41
    dp[0] = 0
    dp[1] = 1

    fib(n)
    print(*result)

• 두 번째 방법
• DP 를 이용해서 피보나치를 푸는 것이 아닌 DP 를 이용해서 문제를 풀기 (0,1 출력 개수 구하기 문제)

• 예를 들어 N = 5 라면, 이것은 4,3 을 호출하는 것과 같음. 따라서 4일 때의 0과 1의 호출개수와 3일 때의 0과 1의 호출개수를 각각 더하면 5일 때 0과 1의 호출개수를 구하는 셈이됨. 결국 0 또는 1 까지 도달하므로 0과 1일 때의 값을 초기화한 후 DP 적용
  

# dp[i][j] -> i = N, j = 0, 1

import sys
        
test_n = int(sys.stdin.readline())

for _ in range(test_n):
    n = int(sys.stdin.readline())
    dp = [[0,0] for _ in range(41)]

    dp[0] = [1,0]
    dp[1] = [0,1]

    for i in range(2,41):
        dp[i][0] = dp[i-1][0] + dp[i-2][0]
        dp[i][1] = dp[i-1][1] + dp[i-2][1]
    
    print(*dp[n])

3. Learned

• 될지 안될지 확신이 없다면 일단 구현해보고 틀린 것을 확인한 후에 다른 접근법을 사용하자

---

No. 14891

1. Problem

2. My Solution

• 톱니바퀴의 회전을 구현하기 위해 deque 자료구조 사용
• 오른쪽 회전은 popleft -> append
• 왼쪽 회전은 pop -> appendleft
• 해당 톱니바퀴를 회전시켰는지에 대한 정보를 visited 에 저장하면서 재귀를 수행

import sys
from collections import deque

def turn(num, direction):

    visited[num] = True
    left, right = gear[num][6], gear[num][2]

    # 오른쪽 회전
    if direction == 1:
        gear[num].appendleft(gear[num].pop())
    # 왼쪽 회전
    else:
        gear[num].append(gear[num].popleft()) 

    # 현재 톱니바퀴의 왼쪽 극성과  왼쪽 톱니바퀴의 오른쪽 극성이 다르다면
    if num-1 >= 0 and visited[num-1] == False and left != gear[num-1][2]:
        turn(num-1, direction * -1)
    
    # 현재 톱니바퀴의 오른쪽 극성과 오른쪽톱니바퀴의 왼쪽 극성이 다르다면
    if num+1 < 4 and visited[num+1] == False and right != gear[num+1][6]:
        turn(num+1, direction * -1)


gear = []
score = [1,2,4,8]
answer = 0

for i in range(4):
    gear.append(deque(map(int,sys.stdin.readline().rstrip())))

k = int(sys.stdin.readline())

for _ in range(k):
    i, j = map(int,sys.stdin.readline().rstrip().split())
    visited = [False] * 4
    turn(i-1, j)

for i in range(4):
    answer += gear[i][0] * score[i]

print(answer)