class4https://www.acmicpc.net/problem/1629    # 문제자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오. # 예제입력 :  첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.10 11 12 출력 :  첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.4 # 필요개념문제를 봤을 때 간단한데 ? 생각했다가 제한시간이 0.5초인 것을 보고 쉽진 않겠다는 생각을 했다. 단순히 Math.pow() 함수를 사용하면 시간초과가 발생한다. pow를 사용하면 최악의 경우 n = 21억이 되므로 O(n) 시간복..

Class 3+ 에센셜https://www.acmicpc.net/problem/1697  # 문제수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. # 예제입력 :  첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.5 17 출력4 # 필요..

알고리즘 스터디 (투포인터)https://www.acmicpc.net/problem/20922  # 문제홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 K$K$개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다. 100000$100\,000$ 이하의 양의 정수로 이루어진 길이가 N$N$인 수열이 주어진다.  이 수열에서 같은 정수를 K$K$개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자. # 예제입력 : 첫째 줄에 정수 N$N$ (1≤N≤200000$1 \le N \le 200\,000$)과 K$K$ (1≤K≤100$1 \le K \le 100$)가 주어진다.둘째 줄에..

https://www.acmicpc.net/problem/1309  # 문제어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다.이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다.동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다. # 예제입력 :  첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다.4 출력 :  첫째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력하여라.41 ..

https://www.acmicpc.net/problem/1495  # 문제Day Of Mourning의 기타리스트 강토는 다가오는 공연에서 연주할 N개의 곡을 연주하고 있다. 지금까지 공연과는 다른 공연을 보여주기 위해서 이번 공연에서는 매번 곡이 시작하기 전에 볼륨을 바꾸고 연주하려고 한다.먼저, 공연이 시작하기 전에 각각의 곡이 시작하기 전에 바꿀 수 있는 볼륨의 리스트를 만들었다. 이 리스트를 V라고 했을 때, V[i]는 i번째 곡을 연주하기 전에 바꿀 수 있는 볼륨을 의미한다. 항상 리스트에 적힌 차이로만 볼륨을 바꿀 수 있다. 즉, 현재 볼륨이 P이고 지금 i번째 곡을 연주하기 전이라면, i번 곡은 P+V[i]나 P-V[i] 로 연주해야 한다. 하지만, 0보다 작은 값으로 볼륨을 바꾸거나, M..

https://www.acmicpc.net/problem/1660  # 문제캡틴 이다솜은 자신의 해적선에 적을 공격하기 위한 대포알을 많이 보관해 놓는다. 다솜이는 미적감각이 뛰어나기 때문에, 대포알은 반드시 사면체 모양으로 쌓아놓아야 한다고 생각한다. 사면체를 만드는 방법은 길이가 N인 정삼각형 모양을 만든다. 그 위에 길이가 N-1인 정삼각형 모양을 얹고 그위에 계속 해서 얹어서 1크기의 정삼각형 모양을 얹으면 된다.예를 들어, 사이즈가 3크기의 한 더미 모양은 다음과 같다. X X X X X X XX X X각각의 삼각형은 1, 3, 6, 10 ,..... 와 같이 대포알을 가지고 있다. 따라서 완벽하게 쌓았을 때, 한 사면체에는 1, 4, 10, 20 ,.... 개를 가지고 있을 것이다.현재 ..

알고리즘 분류 - DPhttps://www.acmicpc.net/problem/1149  # 문제RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.1번 집의 색은 2번 집의 색과 같지 않아야 한다.N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. # 예제입력 :  첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, ..

알고리즘스터디 (dp)https://www.acmicpc.net/problem/22871  # 문제 N$N$개의 돌이 일렬로 나열 되어 있다. N$N$개의 돌에는 왼쪽부터 차례대로 수 A1A2...Ai...AN$A_{1} A_{2} ... A_{i} ... A_{N}$로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 한다.항상 오른쪽으로만 이동할 수 있다. i$i$번째 돌에서 j(i$j(i 번째 돌로 이동할 때 (j−i)$(j - i)$ × (1 + |Ai−Aj$A_{i} - A_{j}$|) 만큼 힘을 쓴다.돌을 한번 건너갈 때마다 쓸 수 있는 힘은 최대 K$K$이다.가장 왼쪽 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너갈 수 있는 모든 경우 중 K$K$의 최솟값..

알고리즘 스터디 - dphttps://www.acmicpc.net/problem/9465  # 문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다.상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다.모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 (b)와 같이 각 스티커에 점수를 매겼다. 상냥이가 뗄 수 있는 스티커의 점수의 최댓..

solved ac (실버1)https://www.acmicpc.net/problem/11660 # 문제N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.1234234534564567 여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.  # 예제입력 :  첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024..