https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 정답 코드 from collections import deque from itertools import chain from sys import stdin M, N, H = map(int, stdin.readline().split()) board = [] queue = deque() for h in range(H): temp = [] for n in range(N): temp..

https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A target: continue else: queue.append((num * 2, c..

https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net 정답 코드 from sys import stdin read = stdin.readline N = int(read()) arr = list(map(int, read().split())) dp = [0] * N dp[0] = arr[0] for i in range(1, N): dp[i] = arr[i] for j in range(i): if ..

1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 접근 방법 연속된 수를 더해서 가장 큰 수를 만드는 경우를 찾아야한다. 주어진 배열의 숫자 중 음수가 있기 때문에 이를 더하더라도 최대 합을 만들 수 있는 경우를 찾아야한다. 아래 메모는 주어진 테스트케이스를 실제로 더해본 과정을 나타낸다. arr 은 주어진 입력이고, dp 의 각 원소는 연속된 합을 나타낸다. dp[i] 의 값은 arr 의 첫번째 원소부터 차례로 더해가면서 업데이트 된다. 즉 dp[i] 의 값은 dp[i - 1] + arr[i] 가 되는 셈이다. 중요한 ..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 정답 코드 import sys N = int(sys.stdin.readline()) arr = list(map(int, sys.stdin.readline().split())) dp = [1] * N for i in range(N): for j in range(i): if arr[j] < arr[i]: dp[i] = ma..

https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 정답 코드 (속도 빠름) def solution(): visited = [] queue = [[N, [N]]] while queue: number, path = queue.pop(0) if number == 1: print(queue) print(len(path) - 1) print(" ".join(map(str, path))) break if number not in visited: visited.append(number) if number % 3 == 0: queue.append([number //..

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 요약 주어진 N개 숫자로 이뤄진 배열의 값을 더하여, K 를 만드는 경우를 구하라 (배열의 숫자는 중복하여 더해도 된다) 정답 코드 N, K = map(int, input().split()) arr = [] for _ in range(N): arr.append(int(input())) dp = [0] * (K + 1) dp[0] = 1 for a in arr: for j in range(a, ..

https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 오답 코드 테스트 케이스는 모두 맞췄길래 정답인줄 착각했다. from math import sqrt N = int(input()) n = N count = 0 while N > 0: if int(sqrt(n)) == sqrt(n): N -= n count += 1 n = N else: n -= 1 print(count) 반례는 12 를 입력할 때인데, 위 코..

https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 사고 과정 1. M 이랑 매칭될 때까지 차례로 더하거나 2. M 보다 커지면 break 3. 어떻게 M 을 맞추느냐는 관심없다. 연속된 숫자의 몇가지 경우가 M 을 맞추는지가 중요. 정답 코드 from sys import stdin N, M = map(int, stdin.readline().split()) arr = list(map(int, stdin.re..