[백준]230118 문제풀이

1629. 곱셈

A, B, C = map(int, input().split())
a = A
b = B

while True:
    if b == 1:
        a = a % C
        break
    elif b % 2 == 0:
        a = (a * a)% C
        b = b // 2
    elif b % 2 == 1:
        a = ((a * a) * A) % C
        b = b // 2

print(a)

원래 분할 정복으로 푸는 문제이고, 구글에 나와있는 풀이도 전부 재귀함수를 사용해 쉽게 구현한다.

나는 아직 재귀함수를 써본 적이 없어서 분할 정복의 개념만 대충 이용해서 반복문으로 풀어보려고 했는데, 논리는 맞는 것 같은데 이상하게 답이 안나온다. 혹시 이 글을 본 능력자가 왜 답이 안나오는지 아신다면 알려주시길...

 

2512. 예산

def mid(a, b):
    if (a + b) % 2 == 1:
        return (a + b) // 2 + 1
    else:
        return (a + b) // 2

num_city = int(input())
list_input = list(map(int, input().split()))
cities_input = list_input
budgetsum = int(input())

b_limit = mid(min(cities_input), max(cities_input))

while True:
    cities = cities_input # 리스트 인풋을 계속 받지 않도록 global에서 리스트를 따로 빼둠
    for i in range(len(cities)):
        if cities[i] > b_limit:
            cities[i] = b_limit

    if sum(cities) == budgetsum:
        break
    elif sum(cities) < budgetsum:
        if sum(cities) + num_city > budgetsum:
            break
        else:
            b_limit = mid(b_limit, max(cities_input))
            continue
    elif sum(cities) > budgetsum:
        b_limit = mid(b_limit, min(cities_input))
        continue

print(b_limit)

이분 탐색도 건드려봤는데, 로직 자체가 이상하게 만들어졌다고 한 소리 들었다. 일단 욕심부리지 말고 쉬운 난이도 알고리즘부터 풀어나가봐야 할듯..

 

23842. 성냥개비

num_list = [[0, 6],[1, 2],[2, 5],[3, 5],[4, 4],[5, 5],[6, 6],[7, 3],[8, 7],[9, 6]]
stick_list = []
answer = int(input()) - 4
ok = 0

for i in range(100):
    for j in range(10):
        if i // 10 == num_list[j][0]:
            a = num_list[j][1]
        if i % 10 == num_list[j][0]:
            b = num_list[j][1]
    stick_list.append([i, a + b])

print(stick_list)

for i in range(100):
    for j in range(100):
        for k in range(100):
            if i + j == k:
                if stick_list[i][1] + stick_list[j][1] + stick_list[k][1] == answer:
                    a, b, c = i, j, k
                    ok += 1
def zero(a):
    if a < 10:
        return f'0{a}'
    else:
        return a

if ok > 0:
    print(f'{zero(a)}+{zero(b)}={zero(c)}')
else:
    print('impossible')

그래서 풀어본 BFS 문제, 너무 노가다로 풀었나 싶기도 한데 일단 맞았으니 OK. 머리 쓰지 않고 0~99에 해당하는 성냥개비 갯수 대응시킨 2차원 리스트 만들고  3중 for문으로 수 3개 찾고 한자리 수는 두자리 수로 만드는 함수를 구현하는 식으로 마무리 했다. 논리가 한번에 먹혀서 행복했다.