👩🏻💻 문제링크 https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net ✍️ 아이디어 1. 문제 이해 문제를 처음에 이해하지 못해서 그냥 강의를 들었다 문제는 n x n 크기에 여러 색의 사탕을 놓고 인접한 곳의 사탕의 색이 다르면 둘을 바꿔서 전체에서 사탕 색이 몇개나 연속되는지 구한다 2. 배열에서 최대 몇개까지 연속되는지 찾게 해주는 함수를 만듬 3. 로직 사탕 색이 가로로or세로로 다른 사탕들을 바꾼다 사탕이 같은 색깔로 최대 몇개까지 연속으로 나오는지 구한다 바꿨던 사탕들을 원위치 시킨다 ✍️소스코드 구현하는데에 애먹음 #include #include #in..
PS 연습
👩🏻💻 문제링크 https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net ✍️ 아이디어 1. 문제 이해 RGB 거리 1과 비슷해 보이지만 마지막 집이 첫번째 집과 이웃한다는 점이 다르다 가장 싸게 모든 집을 페인트칠 하는 알고리즘 근데 인접한 집은 다른 색으로 페인트칠 해야함 앞집이 빨초파 인 경우로 나눠야함 앞집이 빨간색이면 다음집은 초록과 파란집중에 작은것을 골라야함 2. 난 처음에 백트래킹 처럼 어떤 집을 선택하였는지..
👩🏻💻 문제링크 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net ✍️ 아이디어 1. 문제 이해 저점에서 올라갔다가 최고점 찍고 내려오는 최대 긴 수열의 항의 갯수를 구하는것임 (∧ 이런 크기로 수열이 정렬되어야함) 2. 나는 2차원 배열을 이용하여 배열의 한 요소가 내려가는 중인 경우와 올라가는 중인 경우를 나눠서 1) 올라가는 중인 경우 : 자신 보다 작은 수랑만 비교 할수 있음 2) 내려가는 중인 경우 : 자신보다 작고 큰수 둘다 비교 할수 있음 ✍️소스코드..
👩🏻💻 문제링크 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net ✍️ 아이디어 1. 문제 이해 포도주 n개가 일렬로 정렬되어 있고 각 잔에 들어있는 포도주의 양을 입력받을때 포도주를 가장 많이 먹을때 얼마나 먹는가 조건 : 인접한 포도주 3잔을 연속으로 들이키면 안됨 2. 나는 조건을 2개로 생각해 3차원 배열을 만듬 (2번째는 바로 전 포도주를 마신여부, 3번째는 전전 포도주를 마신 여부) 3. 생각보다 케이스가 복잡함 첫 잔을 안마시는 경우..
👩🏻💻 문제링크 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net ✍️ 아이디어 1. 문제 이해 동물원과 비슷한 문제임 스티커를 뜯는데 인접한 곳의 스티커는 못씀 2. D[N][2] = 2행 N열의 스티커로 얻을수 있는 최대 정수 (0인경우 위에 스티커 사용, 1인경우 아래 스티커 사용, 2인경우 N열 스티커 사용 안함) 3. 처음에 스티커 사용 안하는것에 구현을 애먹었는데 그냥 이전 result에서 max 구하면 되는거였음 4. 나..
👩🏻💻 문제링크 https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net ✍️ 아이디어 1. 문제 이해 0~N까지 정수 K개를 더해서 그 합이 N이 나오는 경우의 수를 구하자 2. 점화식 D[N][K] = 0~N까지 정수 K개를 더해서 그 합이 N이 나오는 경우의 수 3. ex) 6까지 정수 4개를 더해서 합이 6 = 6까지 정수 3개를 더해서 + 5까지 정수 3개를 더해서 + 4까지 정수 3개를 더해서 .....+ 0까지 정수 3개를 더해서 (이 아이디어는 내가 직접 떠올림 !) 4. 처음에 n=0, k=0~200 의 값이 1이라는 점을 간과함 ✍️소스코드 내 코드 #incl..
👩🏻💻 문제링크 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net ✍️ 아이디어 1. 문제 이해 연속해서 더할수 있는 수중에 가장 큰 수를 찾자 2. 점화식 D[ i ] = i번째 수로 끝나는 가장 큰 연속합 3. i번째 수열과 i-1번째 점화값과 i번째 수열을 더한 것중에 큰것을 저장한다 A[i] < A[i]+result[i-1] //A[i]는 수열 result는 값 저장 공간 ✍️소스코드 이 아이디어는 강의 안봤으면 절대 안떠올랐을거 같다..(남의 코..
👩🏻💻 문제링크 https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net ✍️ 아이디어 1. 문제 이해 부분수열 1에서 수열을 출력하는것 까지 함 2. 저장할 배열을 하나 더 만들어서 어떠한 값 때문에 자신의 값이 1 증가 했는지 인덱스를 기록 = 백트래킹 3. 백트래킹 : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말합니다. 최적화 문..
