문제수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.입력첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)출력첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.예제 입력 1 610 20 10 30 20 50예제 출력 1 4증가부분수열에서 특정 원소가 마지막 값이 되려면, 그 원소보다 작은 값들로만 이루어진 수열의 끝에 추가되어야 한다. 따라서 A[i]를 마지막으로 하는 ..
분류 전체보기
미로 만들기문제홍준이는 미로 안의 한 칸에 남쪽을 보며 서있다. 미로는 직사각형 격자모양이고, 각 칸은 이동할 수 있거나, 벽을 포함하고 있다. 모든 행과 열에는 적어도 하나의 이동할 수 있는 칸이 있다. 홍준이는 미로에서 모든 행과 열의 이동할 수 있는 칸을 걸어다녔다. 그러면서 자신의 움직임을 모두 노트에 쓰기로 했다. 홍준이는 미로의 지도를 자기 노트만을 이용해서 그리려고 한다.입력으로 홍준이가 적은 내용을 나타내는 문자열이 주어진다. 각 문자 하나는 한 번의 움직임을 말한다. ‘F’는 앞으로 한 칸 움직인 것이고, ‘L'과 ’R'은 방향을 왼쪽 또는 오른쪽으로 전환한 것이다. 즉, 90도를 회전하면서, 위치는 그대로인 것이다.입력첫째 줄에 홍준이가 적은 내용의 길이가 주어진다. 길이는 0보다 크고..
문제풀이코너 A를 몇 번 방문해도 되는지 수식으로 구한 후, A - B가 큰 값부터 해당 개수만큼 차례대로 선택하면 된다. A - B가 음수일 때는 B를 선택함에 유념한다. 필자는 A - B에 대한 배열을 추가적으로 구현하여, 해당 배열을 정렬 후 일정 금액 초과는 반드시 선택, 일정 금액은 남은 선택 개수만큼 선택하는 방식으로 구현하였다. 코드#include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n, x; cin >> n >> x; int cnt = (x - 1000 * n) / 4000; int arr[100000][2]; int diff[100000]; for (int i = 0; i cin >> ar..
문제https://www.acmicpc.net/submit/5585풀이- 거슬러 줄 돈을 계산 후 큰 동전부터 나눔chg = 1000 - int(input())coins = [500, 100, 50, 10, 5, 1]cnt = 0for c in coins: cnt = chg // coin chg %= cprint(cnt)
문제알고리즘난이도 별로 정해진 개수만큼 문제를 골라서 전체 시간을 최소화하는 문제이다.난이도를 증가시키는 경우 60분이 필요하므로 240분은 무조건 소요가 된다.시간을 최소화하려면, 해당 난이도에서 최소 시간으로 문제를 고른뒤에 해당 문제를 오름차순 정렬해서 차이가 최소화 되도록 하면 된다.먼저, 문제를 입력받고 해당 문제들을 난이도 별로 나눈다.난이도마다 오름차순으로 정렬후에 선택해야 하는 문제수만큼 작은것부터 고른다. 그렇다면 해당 난이도에서 휴식시간을 계산하기 위해 오름차순정렬해서 반복문을 할 필요없이 선택된 문제중에 최대값과 최소값의 차이로 휴식시간을 계산해 주면 된다.코드import sysinput = sys.stdin.readlinen = int(input())p = list(map(int, ..
T = int(input())for i in range(T): stack = [] a=input() for j in a: if j == '(': stack.append(j) elif j == ')': if stack: stack.pop() else: # 스택에 괄호가 없을경우 NO print("NO") break else: # break문으로 끊기지 않고 수행됬을경우 수행한다 if not stack: # break문으로 안끊기고 스택이 비어있다면 괄호가 다 맞는거다. print("YES")..
문제 https://www.acmicpc.net/problem/23559 제주대 학생회관 식당에는 두 개의 메뉴가 있다. 코너 A로 가면 5,000원짜리 메뉴를 먹을 수 있고, 코너 B로 가면 1,000원짜리 메뉴를 먹을 수 있다.준원이는 대면 수업이 시작되는 바람에 이제 남은 학기의 N일동안 매일 학식의 두 메뉴 중 정확히 하나를 골라서 먹어야 한다. N일간의 두 메뉴는 이미 공지되어 있고, 준원이는 이미 모든 날의 각 메뉴가 얼마나 맛있을지 수치를 매겨 두었다.준원이는 N일간 학식에 총 X원 이하를 써야 한다.여러분이 N일간 준원이의 메뉴를 잘 골라서, 고른 메뉴의 맛의 합을 최대화 해주자! 입력첫째 줄에는 두 정수 $N$, $X$가 주어진다.둘째 줄부터 $N$개의 줄에, 각 날에 먹을 수 있는 5,..
문제 풀이 부동소수점 문제로 인해 컴퓨터에서 단순한 나누기 방식으로는 21번째 자리까지 정확하게 출력할 수 없다.인간이 사고하는 것과 같은 방법으로 컴퓨터에게 연산을 하게끔 코드를 작성하면 답을 출력할 수 있다. 코드
11059번: 크리 문자열def main(): s = list(input().strip()) n = len(s) flag = 0 dp = [0]* n dp[0] = int(s[0]) for i in range(1,n): dp[i] = dp[i-1]+int(s[i]) # print(dp) if n % 2 > 0 : n-=1 while n>0: for i in range(len(s)-n+1): x = n //2 +i # 절반이 존재하는 위치. 8자리면 4. x-1과 x사이가 절반이겟지... # print(x,i,n) # print(dp[x-1] ,dp[n+i-1]-dp..
문제666은 종말을 나타내는 수라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈 4, 스타워즈 5, 스타워즈 6과 같이 이름을 지었고, 피터 잭슨은 반지의 제왕을 만들 때, 반지의 제왕 1, 반지의 제왕 2, 반지의 제왕 3과 같이 영화 제목을 지었다. 하지만 숌은 자신이 조지 루카스와 피터 잭슨을 뛰어넘는다는 것을 보여주기 위해서 영화 제목을 좀 다르게 만들기로 했다.종말의 수란 어떤 수에 6이 적어도 3개 이상 연속으로 들어가는 수를 말한다. 제일 작은 종말의 수는 666이고, 그 다음으로 큰 수는 1666, 2666,..
문제https://www.acmicpc.net/problem/2230 풀이1. 수열 오름차순 정렬2. 투 포인터로 탐색3. arr[right] - arr[left]가 M 이상이 되는 순간 최소 차이 후보로 갱신4. arr[right] - arr[left] input = __import__('sys').stdin.readlineN, M = map(int, input().split())arr = [int(input()) for _ in range(N)]arr.sort()left = 0right = 0min_diff = float('inf')while right right: right = leftprint(min_diff)
문제 https://www.acmicpc.net/problem/10211 크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있다.여러분은 N과 배열 X가 주어졌을 때, X의 maximum subarray의 합을 구하자. 즉, max1 ≤ i ≤ j ≤ N (X[i]+...+X[j])를 구하자. 입력 입력 파일의 첫 번째 줄에 테스트 케이스의 수를 의미하는 자연수 T가 주어진다. 그 다음에는 T개의 테스트 케이스가 주어진다.각 테스트케이스 별로 첫 번째 줄에 배열의 크기 N이 주어진다. (1 ≤ N ≤ 1,000)그리고 두 번째 줄에..
