개발자일걸요..?

문제링크 : www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 1. 위에 조건이 3가지로 나와있지만, 결국은 모든 집에 있어 양 옆집과 색깔이 달라야한다는 뜻이다. 2. 앞서 같은 색을 몇 번 칠했든 양 옆집과 색이 다르고 최소값이면 채택. 1. 첫 번째 집부터 그 집이 R색일경우, G색일 경우, B색일 경우로 나눠 동시에 3가지 경우를 고려함 2. 0~N번째 집까지 자신의 색깔을 결정하는데 있어 앞집 색을 고려해 앞집과 같은 색의 경우를..

문제링크 : www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net - 기본적으로 2579번(2021.03.24 - [Baekjoon Online Judge] - 2579번 계단오르기)과 유사 - 2579번과는 다르게 0번~N-1번까지 꼭 선택해야하는 잔은 없으므로 입력은 모두 3칸씩 밀려받아, 0번부터 같은 점화식으로 고려한다. - 2579번과 같은 점 : 이전 두 잔을 선택했다면 현재 잔은 선택 불가, 잔의 합을 최대로 만들어야함. 2579번과 다른 점 : 257..

문제링크 : www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 1) 각 칸에서 이동가능한 칸들의 합에서 제일 큰 값을 넣는 배열 dq생성 2) 0번째, 1번째, 2번째는 이 후의 점화식과는 다른 경우의 수이기 때문에 따로 설정 2-1) 0번째 칸까지 고려한 경우, 최대 dq값은 0번째 계단 값 2-2) 1번째 칸까지 고려한 경우, 최대 dq값은 1번째 계단값 or (0번째 계단값+1번째 계단값) 중 큰 값 2-3) 2번째 칸까지 고려한 경우, 최대 dq값은 (0번째 + 2..

문제링크 : www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 1) 입력받은 수를 넣는 배열 number과는 별도의 숫자들의 합을 넣을 배열 dq를 생성 2) for문을 통해 dq의 i번째 값으로 number[i]와 dq[i-1]+number[i]중 더 큰값을 삽입 여기서, dq[i-1]과 number[i]를 더하는 값은 이제까지 제일 큰 값에 지금 고려하는 값을 넣은 경우이고, 그냥 number[i]는 이제까지의 값은 버리고(지금 값을 더 작게 만드는 값이기에) 새값을..

문제링크 : www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 1) 물건들의 무게와, 가치를 입력받은 후, 무게기준 오름차순으로 정렬 2) 무게당 넣을 수 있는 최대가치 계산을 위한 이차배열 dq를 생성 3) dq의 열은 0~K까지로 고려하는 무게, 행은 0~N까지로 고려의 대상이 되는 물건의 개수를 의미함 4) dq의 행=0인 경우 => 고려대상이 되는 물건의 개수가 0, 열=0인경우 => 가..

문제링크 : www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 1) 주어진 문자열을 A, B로 가정. CS들의 배열 cs 생성 2) 두 문자열의 마지막 요소끼리 비교 2-1) A[-1] == B[-1]이라면, 공통 부분 수열 CS의 일부로 채택하고, A[-1]과 B[-1] 삭제 2-2) A[-1] != B[-1]이라면, 2-2-1) A[-1]을 삭제하고 다시 2)로 돌아가 비교 2-2-2) B[-1]을 삭제하고 다시..

문제링크 : www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 1) 전깃줄의 양쪽 포인트를 입력받고, A 전봇대의 point를 기준으로 정렬한다.(오름차순) 2) 이렇게 정렬했을 때, 전깃줄 간의 교차가 없으려면 B전봇대의 point들은 A전봇대처럼 순차적으로 커져야 한다. 3) LIS 알고리즘을 이용하여 자신포함, 자신 앞에 순차적으로 된 전기줄의 숫자를 세어 dq에 기록 4) 전체 전깃줄 수 - dq의 최댓값(전깃줄이 교차없이 이어진 최대의 경우의 수) 를 출력(..

문제링크 : www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 이 문제에서는 1) 왼쪽(index = 0)에서부터 자신보다 작은 수가 몇개인지 세는 수열 dq1 2) 오른쪽(index= N-1)에서부터 자신보다 작은 수가 몇개인지 세는 수열 dq2 3) 자신보다 양쪽(dq1+dq2)에 작은 수가 몇개인지 세는 수열 dq3 이렇게 세개의 수열이 필요하다. 자신보다 작은 수가 몇개인지 세는 방법은 앞서한 11053번 문제를 참고해야한다. dq3를 통해 우리는 각 칸의 값이 양쪽으로 ..

문제 링크 : www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net : 각 수열의 요소를 돌면서 자신의 앞에 자신보다 작은 수가 몇개나 있는 지 확인해 dq에 기록한다. 단, 이때 중복되는 숫자들이 있을 수 있으므로 숫자 자체를 비교하여 dq를 기록하기보단, 숫자를 비교한 후 조건에 충족되면 indexd의 dq값끼리 비교하여 큰수를 dq에 재기록한다. ex) 주어진 예제 6 10 20 ..

문제 링크 : www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 1) 배열을 이용하여 (행=자리수, 열=자리당 i번째 숫자가 올때 계단수의 가짓수) 1자리일때~ N자리일 때까지를 구함 2) 해당 행열의 값은 열의 index가 첫자리에 왔을때의 경우의 수이기 때문에 최종 결과값을 더할때 0열은 더하지 않는다. ex ) N =5 일때의 값을 구한다. 1) 1자리 수일때의 경우는 정해져 있기에 미리 초기화 0 1 2 3 4 5 6 7 8 9 0 1 1 1 1 1 1 1 1 1 1 1 2 3 4 5 2) 2자리 수일 때의 경우는 1자리 수일때 경우 고려해서 계산 2자리 수의 경우 ..