exp_blog

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제 입력 1

5 17

예제 출력 1

4

from collections import deque
MAX = 100001
n, k = map(int, input().split())
array = [0] * MAX

def bfs():
    q = deque([n])
    while q:
        now_pos = q.popleft()
        if now_pos == k:
            return array[now_pos]
        for next_pos in (now_pos - 1, now_pos + 1, now_pos * 2):
            if 0 <= next_pos < MAX and not array[next_pos]:
                array[next_pos] = array[now_pos] + 1
                q.append(next_pos)


>>>print(bfs())

생각해봤는데 dfs 랑 bfs를 언제쓸까라는 생각을 해보았다

결론적으로

• DFS :  방문해야하는 노드의 수가 많고 / 모든 노드의 수를 방문해야할 때
• BFS : 최단 거리 등 내가 원하는 노드만 방문해야할 때

이렇게 나눠서 쓰는게 맞는 거 같다 ㅎㅎ

문제

지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다.

어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다.

그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) 또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열을 만들 수 있다.

우리의 목표는 N이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다. 단 타일들은 무한히 많은 것으로 가정하자.

입력

첫 번째 줄에 자연수 N이 주어진다.(N ≤ 1,000,000)

출력

첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.

예제 입력 1

4

예제 출력 1

5

핵심 

• 사용할 수 있는 타일의 종류 : 2개
• 두 가지 종류의 타일을 이용, N 길이의 수열 만드는 모든 경우의 수 구함
• 동적 프로그래밍
• N이 최대 1,000,000 이므로, 시간 복잡도 O(N) 으로 해결

길이가 짧은 경우 부터 먼저 계산 하고 (특정 리스트에 저장 해놓고)-> 길어지는 것을 뒤에서 계산 하는 것이 좋음 

점화식(인정합 항들 사이의 관계식) 을 세워야 한다

D[i] = "수열의 길이가 i일 때의 경우의 수" / ex) D[3] = 3, D[4] = 5

타일을 왼쪽에서 오른쪽으로 이어 붙인다고 가정

길이가 i 인 수열을 형성하는 방법은 두가지

D[i] =  D[i - 1] + D[i - 2]

=> 피보나치 수열과 동일한 문제

n = int(input())
dp = [0] * 1000001
dp[1] = 1
dp[2] = 2
for i in range(3, n+1):
	dp[i] = (dp[i-2] + dp[i-1]) % 15746 #큰 수 대비
print(dp[n])

문제

1부터 N까지의 수를 오름차순으로 쓴 수열 1 2 3 ... N을 생각하자.

그리고 '+'나 '-', 또는 ' '(공백)을 숫자 사이에 삽입하자(+는 더하기, -는 빼기, 공백은 숫자를 이어 붙이는 것을 뜻한다). 이렇게 만든 수식의 값을 계산하고 그 결과가 0이 될 수 있는지를 살피자.

N이 주어졌을 때 수식의 결과가 0이 되는 모든 수식을 찾는 프로그램을 작성하라.

입력

첫 번째 줄에 테스트 케이스의 개수가 주어진다(<10).

각 테스트 케이스엔 자연수 N이 주어진다(3 <= N <= 9).

출력

각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다.

예제 입력 1 

2 3 7

예제 출력 1 

1+2-3

1+2-3+4-5-6+7

1+2-3-4+5+6-7

1-2 3+4+5+6+7

1-2 3-4 5+6 7

1-2+3+4-5+6-7

1-2-3-4-5+6+7

import copy
def recursive(array, n):
    if len(array) == n:
        operators_list.append(copy.deepcopy(array)) #깊은 복사 ; 테스트 케이스마다 다른 형식을 보여줘야 하니까
        return
    array.append(' ')
    recursive(array, n)
    array.pop()

    array.append('+')
    recursive(array, n)
    array.pop()

    array.append('-')
    recursive(array, n)
    array.pop()

test_case = int(input())

for _ in range(test_case):
    operators_list = []
    n = int(input())
    recursive([], n - 1)

    integers = [i for i in range(1, n + 1)]

    for operators in operators_list:
        string = ""
        for i in range(n - 1):
            string += str(integers[i]) + operators[i]
        string += str(integers[-1])
        if eval(string.replace(" ", "")) == 0:
            print(string)
    print()

문제

한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

만약, 2차원 배열의 크기가 2^N * 2^N라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 4등분 한 후에 (크기가 같은 2^(N-1)로) 재귀적으로 순서대로 방문한다.

다음 예는 2^2 * 2^2 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, (r, c)를 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음 그림은 N=3일 때의 예이다.

입력

첫째 줄에 N r c가 주어진다. N은 15보다 작거나 같은 자연수이고, r과 c는 0보다 크거나 같고, 2^N-1보다 작거나 같은 정수이다

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력 1

2 3 1

예제 출력 1

11

예제 입력 2

3 7 7

예제 출력 2

63

Z모양을 구성하는 4가지 방향에 대하여 차례대로 재귀적으로 호출

N,r,c = map(int, input().split(' '))
count = 0

def divide(size, x, y):
    global count
    if size <=2:
        if(x==r and y ==c):
            print(count)
            return
        count+=1
        if(x==r and y+1==c):
            print(count)
            return
        count+=1
        if(x+1 == r and y==c):
            print(count)
            return
        count+=1
        if(x+1 == r and y+1==c):
            print(count)
            return
        count+=1
        return
    divide((size//2), x,y)
    divide((size//2), x, y+(size//2))
    divide((size//2), x+(size//2), y)
    divide((size//2), x+(size//2),y+(size//2))

if __name__ =="__main__":
    divide(2**N,0,0)

--이렇게 돌리면 시간 초과 에러.. ㅜㅜ 

n, x, y = map(int, input().split())

def power2(k): # 두배 만드는 함수
    return 1 << k

def go(n, x, y):
    if n == 1:
        return 2*x+y
    else:
        if x < power2(n-1): # 점점 쪼개진다.
            if y < power2(n-1):# 점점 쪼개진다.
                return go(n-1, x, y)
            else:
                return go(n-1, x, y-power2(n-1)) + power2(2*n-2)
        else:
            if y < power2(n-1):
                return go(n-1, x-power2(n-1), y) + power2(2*n-2)*2
            else:
                return go(n-1, x-power2(n-1), y-power2(n-1)) + power2(2*n-2)*3;

print(go(n,x,y))

이렇게 돌리면 시간 내에 돌아간다!

def Z(n,x,y):
    if n==1:return 0
    if r<x+n//2:
        if c<y+n//2:
            return Z(n//2,x,y) #0분면
        else:
            return Z(n//2,x,y+n//2)+n*n//4 #1분면
    else:
        if c<y+n//2:
            return Z(n//2,x+n//2,y)+n*n//4*2 #2분면
        else:
            return Z(n//2,x+n//2,y+n//2)+n*n//4*3 #3분면
n,r,c=map(int,input().split())
print(Z(2**n,0,0))