문제 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.입력첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.풀이dp배열을 이용한다. 이 때 dp[n]의 의미는 n번째 원소를 포함한 연속 부분합 중 최대값을 뜻한다. dp배열의 첫 번째 원소 값을 입력받은 수열의 첫 번째 값으로 설정하고,..
분류 전체보기
문제명절이 되면, 홍익이 집에는 조카들이 놀러 온다. 떼를 쓰는 조카들을 달래기 위해 홍익이는 막대 과자를 하나씩 나눠준다.조카들이 과자를 먹는 동안은 떼를 쓰지 않기 때문에, 홍익이는 조카들에게 최대한 긴 과자를 나눠주려고 한다.그런데 나눠준 과자의 길이가 하나라도 다르면 조카끼리 싸움이 일어난다. 따라서 반드시 모든 조카에게 같은 길이의 막대 과자를 나눠주어야 한다.M명의 조카가 있고 N개의 과자가 있을 때, 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 구하라.단, 막대 과자는 길이와 상관없이 여러 조각으로 나눠질 수 있지만, 과자를 하나로 합칠 수는 없다. 단, 막대 과자의 길이는 양의 정수여야 한다.입력첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N..
문제 https://www.acmicpc.net/problem/10773Codeimport sysK = int(sys.stdin.readline()) stack = [] sum_v = 0 for i in range(K): num = int(sys.stdin.readline()) if stack and num == 0: stack.pop() else: stack.append(num)print(sum(stack))
문제https://www.acmicpc.net/problem/15813풀이* 첫 번째 줄에는 이름의 길이가, 두 번째 줄에는 이름이 주어진다.* 각 알파벳에 할당된 점수를 합쳐 출력해야 한다.1. 이름의 길이와 이름을 각 변수에 저장한다.2. 이름의 길이만큼 점수를 더하는 작업을 반복해야 한다.3. 알파벳의 점수는 A = 1, B = 2, ... , Z = 26점이므로, 알파벳의 아스키 코드 - 64로 간단히 구할 수 있다.코드 및 설명
문제풀이같은 수를 고를 수 있으므로 M왼쪽에서부터 두 수를 고르고 차이가 M보다 작으면 오른쪽을 한 칸 증가, M보다 크면 왼쪽을 한 칸씩 증가시키면서 더 작은 값이면 갱신을 반복한다.코드
문제KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다. 예를 들어, 주어진 용액들의 특성값이 [-99, -2, -1, 4, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액의 ..
https://www.acmicpc.net/problem/1806알고리즘 분류 누적 합 투 포인터N, S = map(int, input().split()) li = list(map(int, input().split())) left, right = 0, 0 _sum = li[0] min_Dis = float('inf') while 1: if _sum >= S: # 문제 조건에 맞는 경우 / S보다 합이 크므로 left이동, 범위 축소 # 최소 거리 갱신 if min_Dis > (right - left + 1): min_Dis = right - left + 1 # left가 더이상 이동할 수 없을 때 right 이동 if left == right: if right == N-1: break# right 이동 ..
문제로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.로봇 청소기가 있는 방은 N × M 크기의 직사각형으로 나타낼 수 있으며, 1 × 1 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다. 방의 각 칸은 좌표 (r, c)로 나타낼 수 있고, 가장 북쪽 줄의 가장 서쪽 칸의 좌표가 (0, 0), 가장 남쪽 줄의 가장 동쪽 칸의 좌표가 (N − 1, M − 1)이다. 즉, 좌표 (r, c)는 북쪽에서 (r + 1)번째에 있는 줄의 서쪽에서 (c + 1)번째 칸을 가리킨다. 처음에 빈 칸은 전부 청소되지 않은 상태이다.로봇 청소기는 다음과 같이 작동한다.현재 칸이 아..
문제&링크https://www.acmicpc.net/problem/8972 풀이1. 입력받은 숫자에 맞춰서 종수의 아두이노를 움직인다. 이때 9가지의 입력 종류가 있으니 해당 이동을 표현할 수 있는 배열 x와 y를 활용한다.2. 만약 종수의 아두이노가 움직인 자리가 미친 아두이노가 있는 자리라면 바로 게임을 끝내고 이 순간까지 이동했던 횟수를 출력한다. ex) kraj X3. 종수의 아두이노가 움직인 자리가 안전하다면, 미친 아두이노가 움직인다. 이때 미친 아두이노는 8가지의 방법으로 움직일 수 있다. ex) 종수의 아두이노를 기점으로 9번 방향에 존재한다면 무조건 좌하단 방향으로 움직임 -> 제일 가까워지는 방법4. 미친 아두이노가 이동한 후의 자리는 tmp 행렬에 저장하고, check 행렬을 표시한다..
문제https://www.acmicpc.net/problem/11931풀이* 첫 번째 줄에 앞으로 입력받을 정수의 개수가 입력됨* 두번째 줄부터 입력되는 숫자를 내림차순으로 정렬해 출력해야 함1. 첫 번째 줄에 입력받은 정수만큼 반복하며 리스트에 숫자를 추가하고2. 리스트를 내림차순으로 정렬한 뒤3. 리스트에 저장된 숫자를 한 줄마다 출력해야 함코드 및 설명
문제&링크https://www.acmicpc.net/problem/16395 풀이1. 파스칼의 삼각형을 왼쪽으로 붙인다고 생각한다. 그 경우 직각이 왼쪽 하단에 위치한 하삼각 행렬이 된다.2. 첫 번째 열의 모든 값과 열과 행이 같은 모든 값은 1이기에 초기화를 진행한다.3. 2번에 위치하지 않은 값들은 해당 위치의 바로 위(map[i - 1][j])와 왼쪽 대각선 위(map[i - 1][j - 1])를 더해서 만든다.4. 원하는 행 및 열을 찾아 출력한다. 코드#include using namespace std;int map[31][31];int main() { for (int i = 1; i > N >> M; cout
문제 풀이1과 2와 3일 때의 합의 방법의 수를 정의한다.(n을 만드는 가짓수) == (n-3을 만드는 가짓수) + (n-2를 만드는 가짓수) + (n-1을 가짓수)임을 이용하여 코드를 작성한다. (각 가짓수에 각각 3, 2, 1을 더하면 n이 만들어지기 때문)코드T = int(input()) dp = [0] * 10 dp[0] = 1 dp[1] = 2 dp[2] = 4 for i in range(3, 10): dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1] for _ in range(T): print(dp[int(input()) - 1])
