![]()
문제알고리즘해당 배열의 모든 정수쌍의 곱의 합을 구하는 문제이다. 배열이 500000개가 최대이므로 반복문 2개를 사용하면 시간초과가 나오게 된다.이때, 누적합을 사용해주면 된다. 1그러면 누적합을 먼저 계산해주고, 반복문을 통해 i를 설정해준다음에 누적합계산을 통해 (A[i+1] + ... + A[n])을 찾고 곱해주면 된다.코드import sysinput = sys.stdin.readlinen = int(input())arr = list(map(int,input().split()))prefix = [0]*(n+1)for i in range(1,n+1): prefix[i] = prefix[i-1] + arr[i-1]ans = 0for i in range(1,n): ans = (ans + ar..
태상이의 훈련소 생활문제2020년 5월 14일 논산훈련소에 입대한 태상이는 첫 총기 훈련에서 가스 조절기를 잃어버리는 중대한 실수를 범했다. 그로 인해, 태상이는 조교들에게 눈총을 받게 되었다. 조교들은 태상이에게 연병장(운동장)의 흙을 옮기는 일을 주고 제대로 수행하지 못하면 징계를 내리려고 한다.연병장은 일렬로 이어진 N개의 칸으로 이루어져 있으며 각 칸마다 높이를 가지고 있고, 첫 번째 칸부터 순서대로 1번, 2번, 3번, ..., N번 칸으로 명칭이 붙어있다. 조교들은 총 M명이 있으며, 각 조교들은 태상이에게 a번 칸부터 b번 칸까지 높이 k만큼 흙을 덮거나 파내라고 지시한다. 흙은 주변 산에서 얼마든지 구할 수 있으므로 절대로 부족하지 않다.태상이는 각 조교의 지시를 각각 수행하면, 다른 조교..
문제알파벳 소문자와 대문자로만 이루어진 길이가 N인 단어가 주어진다.한 줄에 10글자씩 끊어서 출력하는 프로그램을 작성하시오.입력첫째 줄에 단어가 주어진다. 단어는 알파벳 소문자와 대문자로만 이루어져 있으며, 길이는 100을 넘지 않는다. 길이가 0인 단어는 주어지지 않는다.출력입력으로 주어진 단어를 열 개씩 끊어서 한 줄에 하나씩 출력한다. 단어의 길이가 10의 배수가 아닌 경우에는 마지막 줄에는 10개 미만의 글자만 출력할 수도 있다문제문자열을 한 줄 입력받음.input()을 사용해서 문자열을 통째로 입력받음.10글자씩 자르기 위해 반복문을 돌림.range(0, len(문자열), 10)을 사용해 10칸씩 건너뛰며 반복.슬라이싱을 통해 해당 구간의 10글자를 출력.문자열[i:i+10]처럼 범위를 지정해..
13371번: Dolphindef gkatn(n): left, right = 1, 65536 while left right: mid = (left + right) // 2 total = 3 * mid * (mid + 1) // 2 if total >= n: right = mid else: left = mid + 1 k = left yest = 3*(k-1)*k//2 idx = n- yest - 1 if idx k: return f"{k} dolphin" if k == 1 else f"{k} dolphins" elif idx 2 * k: retu..
![]()
문제https://www.acmicpc.net/problem/15686풀이1. 모든 치킨 집 중에서 M개를 고름.2. M개를 고른 case마다 치킨 거리를 계산.3. 최소 거리를 갱신4. 위 과정을 백트래킹으로 완전 탐색하며 답을 구함. input = __import__('sys').stdin.readlinen, m = map(int, input().split())li = [list(map(int, input().split())) for _ in range(n)]h = []c = []for i in range(n): for j in range(n): if li[i][j] == 1: h.append((i, j)) elif li[i][j] == 2: ..
[코드]#include using namespace std;int d(int n) { //n을 생성자로 하여, n과 n의 각 자리수를 더하는 함수 int sum = n; while (n != 0) { sum += n % 10; n = n / 10; } return sum;}int main() { int arr[10001] = { 0 }; for (int i = 1; i https://www.acmicpc.net/problem/4673문제셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다.양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d..
문제N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 열에 평행해야 한다.입력첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 수가 주어진다.출력첫째 줄에 정답 정사각형의 크기를 출력한다.코드n,m = map(int,input().split())a = min(n,m)I = []for _ in range(n) : I.append(list(map(int, list(input().strip()))))for size in range(a, 0, -1): for i in range(n - size + 1):..
![]()
문제알고리즘백트래킹으로 해결하는 문제이다. 꽃잎이 화단을 넘어간다면 꽃이 죽게되므로 씨앗을 심을수 있는 범위는 화단의 가장자리를 제외하고 계산하면 된다.꽃을 3개를 심으면 재귀가 종료되도록 하고, 다른 경우는 화단의 가장자리를 제외한 경우를 모두 탐색하면서 씨앗을 심고 dx,dy를 통해 꽃잎을 검사하는데, 이때 방문했다( 해당 자리에 미리 심은 씨앗이 있거나 꽃잎이 있는 경우)면 break를 통해 dx,dy반복문을 종료한다. 이때 방문하지 않았다(해당 자리에 미리 심은 씨앗이 없거나 꽃잎이 없는 경우)면 cost를 더해주고 다시 재귀를 반복한다.코드import sysinput = sys.stdin.readlinen = int(input())arr = [list(map(int, input().split()..
문제 https://www.acmicpc.net/problem/18111팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 땅을 파거나 집을 지을 수 있는 게임이다.목재를 충분히 모은 lvalue는 집을 짓기로 하였다. 하지만 고르지 않은 땅에는 집을 지을 수 없기 때문에 땅의 높이를 모두 동일하게 만드는 ‘땅 고르기’ 작업을 해야 한다.lvalue는 세로 N, 가로 M 크기의 집터를 골랐다. 집터 맨 왼쪽 위의 좌표는 (0, 0)이다. 우리의 목적은 이 집터 내의 땅의 높이를 일정하게 바꾸는 것이다. 우리는 다음과 같은 두 종류의 작업을 할 수 있다.좌표 (i, j..
문제명절이 되면, 홍익이 집에는 조카들이 놀러 온다. 떼를 쓰는 조카들을 달래기 위해 홍익이는 막대 과자를 하나씩 나눠준다.조카들이 과자를 먹는 동안은 떼를 쓰지 않기 때문에, 홍익이는 조카들에게 최대한 긴 과자를 나눠주려고 한다.그런데 나눠준 과자의 길이가 하나라도 다르면 조카끼리 싸움이 일어난다. 따라서 반드시 모든 조카에게 같은 길이의 막대 과자를 나눠주어야 한다.M명의 조카가 있고 N개의 과자가 있을 때, 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 구하라.단, 막대 과자는 길이와 상관없이 여러 조각으로 나눠질 수 있지만, 과자를 하나로 합칠 수는 없다. 단, 막대 과자의 길이는 양의 정수여야 한다.입력첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N..
![]()
문제풀이정렬 후 투 포인터 사용 등의 간단한 O(nlgn) 풀이들도 존재한다. (STL은 사기이다!)필자는 O(n)풀이로, 들어오는 숫자를 인덱스로 배열을 증가시키고, 배열에 짝이 맞으면 cnt를 증가시키는 식으로 구현하였다.코드#include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int cnt = 0, n, x, arr[1000010]; fill(arr, arr + 1000010, 0); cin >> n; while (n--) { cin >> x; arr[x]++; } cin >> x; for (int i = 1; i ..
![]()
1935번: 후위 표기식2 from collections import dequedef main(): n = int(input()) arr = deque(input()) dict = [] for _ in range(n): dict.append(int(input())) xrr = deque() while arr: if len(arr)==1: # print(float(xrr[0])) print("{:.2f}".format(xrr[0])) break x = arr.popleft() # print(x) if ord(x) >= 65 and ord(x) ..
