Think Logically Think Logically

문제 링크 : https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. www.acmicpc.net n = int(input()) d = [0] *1001 d[0] = 1 d[1] = 1 for i in range(2,n+1): d[i] = d[i-1] + d[i-2] + d[i-2] d[i] %= 10007 print(d[n]) 앞선 문제에 한 가지 경우(가장 마지막에 할 수 있는 일이 2x2로 채우는 것)가 추가되었다.

문제 링크 : https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net n = int(input()) d = [0]*1001 d[1] = 1 d[2] = 2 for i in range(3,n+1): d[i] = d[i-1]+d[i-2] d[i] %= 10007 print(d[n]) dp는 점화식 세우는 게 핵심인 것 같다.

문제 링크 : https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net n = int(input()) d = [0]*(n+1) for i in range(2,n+1): d[i] = d[i-1] + 1 if i%2 == 0 and d[i] > d[i//2]+1: d[i] = d[i//2]+1 if i%3 == 0 and d[i] > d[i//3]+1: d[i] = d[i//3]+1 print(d[n]) bottom-up 방식으로 풀었다. 파이썬은 재귀를 사용하게 되는 top-down 방식으로 풀면 시간과 메모리 모두 많이 쓴다기에 dp 다시 차근차근 풀어보며 botto..

문제 링크 : https://www.acmicpc.net/problem/3055 3055번: 탈출 문제 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다. 티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나 www.acmicpc.net from collections import deque r,c = map(int,input().split()) woods = [..

문제 링크 : https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다. (1, 1)과 (N, M)은 항상 뚫려있다. www.acmicpc.net from collections import deque m,n = map(int,input().split()) maze = [list(map(int,input())) for _ in range(n)] dx = (-1,1,0,0) dy = (0,0,-1,1) dist = [[-1]*m for _ in range(n)..

문제 링크 : https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 www.acmicpc.net from collections import deque s, sis = map(int,input().split()) ..

문제 링크 : https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다. 화면에 있는 이모티콘 중 하나를 삭제한다. 모든 연산은 1초가 걸린다. 또, 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용 www.acmicpc.net from collections import deque MAX = 1001 s = int(input()) check = ..

문제 링크 : https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민 www.acmicpc.net import sys from copy import deepcopy n, m = map(int,input().split()) ..