넘치게 채우기

https://codeforces.com/contest/2043/problem/AEducational Codeforces Round 173(Div.2) - A. Coin Transformation문제 유형: 재귀, 분할 정복시간 제한: 1초메모리 제한: 256MB 문제Initially, you have a coin with value n">n.You can perform the following operation any number of times (possibly zero):- transform one coin with value x">x, where x">x is greater than 3">3 (x>3">x>3), into two coins with value ⌊x4⌋..

https://www.acmicpc.net/problem/2143BOJ - 두 배열의 합문제 유형: 이진 탐색, 부분합, 정렬문제 난이도: Gold III시간 제한: 2초메모리 제한: 64MB 문제한 배열 A[1], A[2], …, A[n]에 대해서, 부 배열은 A[i], A[i+1], …, A[j-1], A[j] (단, 1 ≤ i ≤ j ≤ n)을 말한다. 이러한 부 배열의 합은 A[i]+…+A[j]를 의미한다. 각 원소가 정수인 두 배열 A[1], …, A[n]과 B[1], …, B[m]이 주어졌을 때, A의 부 배열의 합에 B의 부 배열의 합을 더해서 T가 되는 모든 부 배열 쌍의 개수를 구하는 프로그램을 작성하시오.예를 들어 A = {1, 3, 1, 2}, B = {1, 3, 2}, T=5인 경우..

https://www.acmicpc.net/problem/20040BOJ - 사이클 게임문제 유형: 유니온-파인드, 트리, 서로소-집합문제 난이도: Gold IV시간 제한: 1초메모리 제한: 512MB 문제사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 번호가 부여된 평면 상의 점 n 개가 주어지며, 이 중 어느 세 점도 일직선 위에 놓이지 않는다. 매 차례 마다 플레이어는 두 점을 선택해서 이를 연결하는 선분을 긋는데, 이전에 그린 선분을 다시 그을 수는 없지만 이미 그린 다른 선분과 교차하는 것은 가능하다. 게임을 진행하다가 처음으로 사이클을 완성하는 순간..

https://leetcode.com/problems/minimum-cost-for-tickets/description/leetcode - Minimum Cost For Tickets문제 유형: 다이나믹 프로그래밍문제 난이도: Medium 문제You have planned some train traveling one year in advance. The days of the year in which you will travel are given as an integer array days. Each day is an integer from 1 to 365.Train tickets are sold in three different ways:a 1-day pass is sold for costs[0] dol..

https://www.acmicpc.net/problem/2239BOJ - 스도쿠문제 유형: 백트래킹, 구현문제 난이도: Gold IV시간 제한: 2초메모리 제한: 256MB 문제스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램..

https://www.acmicpc.net/problem/17404BOJ - RGB거리 2문제 유형: 다이나믹 프로그래밍문제 난이도: Gold IV시간 제한: 0.5초메모리 제한: 128MB 문제RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다.N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다.i(2 ≤ i ≤ N-1)번 집의 색은 i-1, i+1번 집의 색과 같지 않아야 한다. 입력첫째 줄에 집의 ..

https://leetcode.com/problems/number-of-ways-to-form-a-target-string-given-a-dictionary/description/leetcode - Number of Ways to Form a Target String Given a Dictionary문제 유형: 다이나믹 프로그래밍, 문자열 처리문제 난이도: Hard 문제You are given a list of strings of the same length words and a string target.Your task is to form target using the given words under the following rules:target should be formed from left to ..

https://www.acmicpc.net/problem/10942BOJ - 팰린드롬?문제 유형:  팰린드롬, 다이나믹 프로그래밍, 투 포인터문제 난이도: Gold IV시간 제한: 0.5초메모리 제한: 256MB 문제명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다.각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다.예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자.S = 1, E = 3인 경우 1, 2, 1은 팰린드롬이다.S = 2..

https://leetcode.com/problems/maximum-sum-of-3-non-overlapping-subarrays/description/leetcode - Maximum Sum of 3 Non-Overlapping Subarrays문제 유형: 슬라이딩 윈도우, 부분합, 다이나믹 프로그래밍문제 난이도: Hard 문제Given an integer array nums and an integer k, find three non-overlapping subarrays of length k with maximum sum and return them.Return the result as a list of indices representing the starting position of each int..

https://www.acmicpc.net/problem/9252BOJ - LCS 2문제 유형: LCS(Longest Common Subsequence), 다이나믹 프로그래밍, 문자열처리문제 난이도: Gold IV시간 제한: 1초메모리 제한: 256MB 문제LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. 출력첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력..