넘치게 채우기

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를 출력..

https://leetcode.com/problems/best-sightseeing-pair/description/leetcode - Best Sightseeing Pair문제 유형: 그리디, 다이나믹 프로그래밍문제 난이도: Medium 문제You are given an integer array values where values[i] represents the value of the ith sightseeing spot. Two sightseeing spots i and j have a distance j - i between them.The score of a pair (i  values[i] + values[j] + i - j: the sum of the values of the sightseein..

https://www.acmicpc.net/problem/18353BOJ - 병사 배치하기문제 유형: LIS(Longest Increasing Subsequence), 다이나믹 프로그래밍문제 난이도: Silver II시간 제한: 1초메모리 제한: 256MB 문제N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며, 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다. 다시 말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다.또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서도 남아있는 병사의 수가 최대가 되도록 하고 싶다.예를 들어, N=7일 때 나열된 병사들의 전투력이 다음과 같..