poorman

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

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

해결 방안 - 1

1. 너비우선탐색(BFS) 알고리즘을 이용하여 N 값이 1이 될때까지 탐색한다.

2. FIFO 큐를 사용하기 위해서 collections.deque를 이용하여 popleft로 값을 꺼낸 후에 새로운 노드를 append한다.

3. 노드 값은 [value, count] 형태로 사용하고 너비 우선 탐색이므로 value가 1이 되는 순간의 count를 리턴한다.

소스 코드 - 1

import sys
from collections import deque
input = sys.stdin.readline

N = int(input())

def BFS(x):
    cnt = 0
    Q = deque([(x,cnt)])
    while(Q):
        x,cnt = Q.popleft()
        if x == 1:
            return cnt
        if x % 3 == 0:
            Q.append([x//3,cnt+1])
        if x % 2 == 0:
            Q.append([x//2,cnt+1])
        Q.append([x-1,cnt+1])
    return -1

print(BFS(N))

수행시간 : 2372ms

해결 방안 - 2

1. 깊이우선탐색(DFS) 알고리즘을 이용하여 N 값이 1이 될때까지 탐색한다.

2. LIFO 스택을 사용하여 pop으로 값을 꺼낸 후에 새로운 노드를 append한다.

3. 노드 값은 [value, count] 형태로 사용하고 value 값이 1이 되는 순간의 count값으로 min_count의 최소 값을 갱신한다.

4. 최소 count 값만 구하면 되기 때문에 min_count보다는 더 깊게 탐색하지 않는다.

5. 깊이 우선 탐색이 모두 끝났을 때 min_count값을 리턴한다.

소스 코드 - 2

import sys
from collections import deque
input = sys.stdin.readline

N = int(input())
def DFS(x):
    min_cnt = x
    cnt = 0
    Q = deque([(x,cnt)])
    while(Q):
        x,cnt = Q.pop()
        if cnt >= min_cnt:
            continue
        if x == 1:
            min_cnt = min(min_cnt, cnt)
        Q.append([x-1,cnt+1])
        if x % 2 == 0:
            Q.append([x//2,cnt+1])
        if x % 3 == 0:
            Q.append([x//3,cnt+1])
    return min_cnt

print(DFS(N))

수행시간 : 1272ms

* 해당 문제는 BFS/DFS의 탐색에 시간이 많이 소요되어 비효율적이다.

해결 방안 - 3

1. 재귀함수를 이용하여 현재 위치에 도달하는 최소 코스트를 리턴한다.

2. 현재 위치의 최소 코스트에 도달하기 위해서는 2,3으로 나누어 떨어지는 거리(x//2,x//3) + 나머지 거리(x%2,x%3) + 1이다. f(x) = min( f(x//3) + x%3 + 1, f(x//2) + x%2 + 1)

3. 거리가 1일때는 0, 거리가 2,3일때는 1의 코스트가 든다. f(1) = 0, f(2) = 1, f(3) = 1

소스 코드 - 3

import sys
input = sys.stdin.readline

N = int(input())
def fnc(x):
    if x == 1:
        return 0
    elif x <= 3:
        return 1
    return min(fnc(x//3) + x%3 + 1, fnc(x//2) + x%2 + 1)
print(DP(N))

수행시간 : 72ms

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

문제

0보다 크거나 같고, 99보다 작거나 같은 정수가 주어질 때 다음과 같은 연산을 할 수 있다. 먼저 주어진 수가 10보다 작다면 앞에 0을 붙여 두 자리 수로 만들고, 각 자리의 숫자를 더한다. 그 다음, 주어진 수의 가장 오른쪽 자리 수와 앞에서 구한 합의 가장 오른쪽 자리 수를 이어 붙이면 새로운 수를 만들 수 있다. 다음 예를 보자.

26부터 시작한다. 2+6 = 8이다. 새로운 수는 68이다. 6+8 = 14이다. 새로운 수는 84이다. 8+4 = 12이다. 새로운 수는 42이다. 4+2 = 6이다. 새로운 수는 26이다.

위의 예는 4번만에 원래 수로 돌아올 수 있다. 따라서 26의 사이클의 길이는 4이다.

N이 주어졌을 때, N의 사이클의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. N은 0보다 크거나 같고, 99보다 작거나 같은 정수이다.

출력

첫째 줄에 N의 사이클 길이를 출력한다.

해결 방안

1. N의 10의 자리 숫자는 N//10 (몫), 1의 자리 숫자는 N%10 (나머지)가 된다.

2. 새로운 수 s는 N의 나머지가 10의 자리 숫자(N%10*10)가 되고,

몫과 나머지를 더한 수의 1의 자리 숫자((N//10 + N%10)%10)가 1의 자리 숫자가 된다.

3. s값으로 1,2를 반복하여 새로운 s값이 N가 같아질 때까지 반복한다.

소스 코드

import sys
input = sys.stdin.readline

N = int(input())
s = N
cnt = 0
while(True):
    x = s//10
    y = s%10
    s = 10*y + ((x+y)%10)
    cnt += 1
    if s == N:
        break
print(cnt)

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

문제

정수 N개로 이루어진 수열 A와 정수 X가 주어진다. 이때, A에서 X보다 작은 수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 X가 주어진다. (1 ≤ N, X ≤ 10,000)

둘째 줄에 수열 A를 이루는 정수 N개가 주어진다. 주어지는 정수는 모두 1보다 크거나 같고, 10,000보다 작거나 같은 정수이다.

출력

X보다 작은 수를 입력받은 순서대로 공백으로 구분해 출력한다. X보다 작은 수는 적어도 하나 존재한다.

해결 방안

1. filter 함수를 이용하여 X보다 작은 수만 필터링한다.

소스 코드

import sys
input = sys.stdin.readline

N,X = map(int, input().split())
A = map(int, input().split())
s = map(str, list(filter(lambda x: x < X, A)))
print(' '.join(s))