하루일문

문제 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 코드 # dfs로 노력해봤으나 시간 관계상 전체탐색 방향을 시간초과로 통과를 하지 못함 # visited는 따로 필요 없는 문제라 사용 X # from collections import deque가 그냥 import deque 보다 빠름 from collections import deque import sys input = sys.stdin.readline # 3차원이니 z를 사용 dz = [0, 0, 0, 0, 1, -1] dx =..

문제 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 코드 def dfs(x): global Queen # 맨 끝 행까지 온 경우 모두 놓을 수 있는 자리이니 += 1 if x == n: Queen += 1 return # 행 기준으로 돈다(행이 겹치지 않도록) for y in range(n): # 열과 좌우 대각선에 겹치는 부분이 없는지 본다 if not visited_1[y] and not visited_2[x+y] and not visited_3[x-y]: # 돌았다면 체크 후 다음 행으로 넘어간다 visited_1[y..

문제 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 코드 n, k = map(int, input().split()) tool = [[0,0]] + [list(map(int, input().split())) for _ in range(n)] bag = [[0] * (k + 1) for _ in range(n+1)] # 전체 물품 수 for i in range(1, n+1): # 가방에 담을 수 있는 최대 무게 for j in range(1, k+..

문제 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 코드 import sys input = sys.stdin.readline k, n = map(int, input().split()) li = [] for i in range(k): li.append(int(input())) # long이 최대 길이는 max(li) short, long = 1, max(li) # short가 long보다 길어지면 멈춰 while short = n: short = cut + 1 # 개수보다 적다면 ..

문제 13777번: Hunt The Rabbit For each line of input, output the numbers of all envelopes opened, in the order they were opened, until the rabbit is found. Each number must be on the same line separated by a space from the previous number. www.acmicpc.net 코드 while True: start, end = 1, 50 N = int(input()) # N이 0이면 반복을 끝낸다 if N == 0: break while True: # start와 end의 중간을 구한다 n = (start + end) // 2 # 중..

문제 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 코드 n = int(input()) stair = [0] score = [0] * (n+1) for i in range(n): stair.append(int(input())) # 한칸에서 두번째 칸은 점화식에서 이용되는 수이자 max값이 바뀔일이 없으니 먼저 설정한다. if i < 2: score[i+1] = sum(stair[0:i+2]) # 설정이 인된 3부터 돌아준다 for i in range(3, n+1): # score[i-2]+stair[i] : 1칸 2칸 ..

문제 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 코드 T = int(input()) li = [] for _ in range(T): li.append(list(map(int, input().split()))) # 1행부터(0행의 수는 하나니까) 아래로 내려간다 for i in range(1, T): # i행의 갯수만큼 for문을 돈다 for j in range(len(li[i])): # j가 T-1 안에 있다면 a는 한 행 위를 저장한다. 아니라면 0을준다.(어차리 아래 max()로 인해 비교되고 탈락할 수) if 0

문제 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 코드 n = int(input()) num = 0 num_li = [0, 1] for i in range(2, n + 1): num = num_li[i-2] + num_li[i-1] num_li.append(num) print(num_li[n]) 해설 그리디 문제이다. 하나하나를 더해서 그 값을 구하는 문제로 리스트에 넣어서 순서에 맞게 더해주는 방식으로 풀이하였다