순간을 성실히, 화려함보단 꾸준함을

https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 해설 : 일단 백트래킹 문제라는 건 바로 알아채려야 합니다. 다만, 좀 까다로운 부분이 두 부분수열이 반복되서 나타나는걸 어떻게 처리를 해주냐???이게 정말 짜증나는 부분인 것 같아요. 이부분은 따로 소스로 적을테니 한번 직접 노트와 펜으로 끄적이면서 익혀보시길 추천드릴게요 중요한건, 내가 방금 추가한 숫자가 모두 '나쁜 수열'을 만들 수 있으면, 이전에 만들었던 수도 다시 뜯어 고쳐야 되는 상황이 발생합니다..

https://www.acmicpc.net/problem/2602 2602번: 돌다리 건너기 첫째 줄에는 마법의 두루마리에 적힌 문자열(R, I, N, G, S 로만 구성된)이 주어진다. 이 문자열의 길이는 최소 1, 최대 20 이다. 그 다음 줄에는 각각 와 를 나타내는 www.acmicpc.net 해설 : 천사 돌다리와 악마 돌다리가 나뉘어져 있으니깐 전 2번 탐색하였습니다. 두루마리에 적힌 문자열대로 번갈아가면서 탐색해야되니, 상태들을 3차원 배열로 표현을 해주면 됩니다. dp[x][y][cnt] = a 문자열을 x번째까지 탐색과 b 문자열을 y번째까지 탐색이 cnt 번째일때 만들 수 있는 경우의 수 만약 현재 내가 찾고자 하는 문자가 맞다면 선택을 하고 다음 돌다리로 가야되니 (i+1,i+1)로 ..

https://www.acmicpc.net/problem/17492 17492번: 바둑알 점프 입력의 첫 줄에 양의 정수 N이 주어진다. 이는 N × N 정사각 행렬의 한 변의 길이이다. 그 다음 줄부터 N개의 줄에 걸쳐 판의 상태가 주어진다. 각 줄은 N개의 정수가 공백으로 구분되어 주어지는 www.acmicpc.net 해설 : 바둑알이 인접한 바둑알을 넘어서면 넘겨진 바둑알은 사라집니다. 이 행위를 반복해서 바둑알을 1개를 만들 수 있냐 없냐를 구하는 문제입니다. https://www.acmicpc.net/problem/9207 9207번: 페그 솔리테어 각 테스트 케이스에 대해서, 핀을 움직여서 남길 수 있는 핀의 최소 개수와 그 개수를 만들기 위해 필요한 최소 이동 횟수를 출력한다. www.acm..

https://www.acmicpc.net/problem/17370 17370번: 육각형 우리 속의 개미 무한히 많은 정육각형이 서로 맞닿아 놓인 형태의 개미 우리가 있다. 다음 그림과 같은 형태이고, 하얀색 변으로만 개미가 다닐 수 있다. 개미 우리의 모습 곤충 관찰이 취미인 유이는 세 정육각 www.acmicpc.net 해설 : 이거 절대 간단한 문제가 아닙니다....(적어도 저는요 ㅠㅠ) 일단 육각형,,,이걸 어떻게 표현해 줄까요??? 여기부터 엄청 꼬이더라구요. 먼저 n의 범위부터 체크해보면 최대가 22입니다. 그말은 즉슨 대각선 ,가로,세로 최대 22번밖에 못간다는 뜻이니 '대충' 적당히 큰 범위를 배열로 선언해 줍시다. 왜 배열로 선언하느냐??? 이미 지나왔던 자취인지 아닌지 알기 위해선 '체..

https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에 www.acmicpc.net 해설 : 트리dp 문제라고는 하는데,,,,,전 점화식을 어떻게 세워야 될지 감이 잘 오질 않습니다 ㅠㅠㅠ 그래서 dfs로만 풀었는데 추후에 업로드를 다시 하겠습니다. 트리가 주어지고 얼리 아답터의 개수를 최소화 시키면 됩니다. 어떤 한 정점이 얼리 아답터라면 그 정점에 연결되어 있는 모든 정점들은 얼리 아답터로 만들어줄 필요가 없겠죠. 곰곰이 생각해보면 "어떤 특..

https://www.acmicpc.net/problem/1262 1262번: 알파벳 다이아몬드 첫째 줄에 N R1 C1 R2 C2가 주어진다. N은 20,000보다 작거나 같은 자연수이고, 0 r2 >> c2; for (int i = 0,s=r1; i = n)cout

https://www.acmicpc.net/problem/14722 14722번: 우유 도시 영학이는 딸기우유, 초코우유, 바나나우유를 좋아한다. 입맛이 매우 까다로운 영학이는 자신만의 우유를 마시는 규칙이 있다. 맨 처음에는 딸기우유를 한 팩 마신다. 딸기우유를 한 팩 마신 후 www.acmicpc.net 해설 : 딸기우유->초코우유->바나나우유 순으로 먹어야 되는데, 꼭 인접한 위치에 있는 우유를 먹을 필요가 없습니다. 따라서 단순한 2차원 테이블로는 해결할 수가 없죠. 바로 위의 우유를 마지지 않더라도 지금까지 먹은 우유중에 가장 최근에 먹은 우유가 순서에 적합하다면 카운트를 시켜줘야 하니까요. 따라서 3차원 테이블로 이를 표현할 수 있습니다. dp[i][j][k] = (i,j)에 위치하고 지금까지..

https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 해설 : 삼성 A형 기출이었는데 천천히 마음 차분하게 한번에 맞는 다는 생각으로 푸시면 할 수 있으실 겁니다. 그게 동작들을 나누어 봐요. 어떤 동작이 높은 우선순위를 가져야 하는지, 그리고 그 과정속에서 필요한 조건들을 뽑아내고 이것들이 다음 동작에 어떻게 미치는지 먼저 적들이 단 한명이라도 확인을 하고 난 후 화살을 쏴야겠죠. 그 다음 화살에 맞은 적들은 보드판에서 지워줘야 하고, 한줄씩 밑으로 내리면 ..

https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 해설 : 대표적인 투포인터 문제입니다. 해당 수만 제외한 배열에서 크면 r-- 작으면 l++ 로 범위를 줄여나아가면 됩니다. #include using namespace std; int arr[2000]; int main() { int n; cin >> n; for (int i = 0; i > arr[i]; sort(arr, arr + n); int cnt = 0; for (int i = 0; i <..

https://www.acmicpc.net/problem/1595 1595번: 북쪽나라의 도로 입력은 여러줄에 걸쳐 주어진다. 입력의 각 줄은 세 개의 양의 정수로 구성되어있는데, 각각은 차례대로 서로 다른 두 도시의 번호와 두 도시를 연결하는 도로의 길이를 의미한다. 모든 도로는 www.acmicpc.net 해설 : 이 문제는 엄청나게 유명한 웰논문제입니다. 그냥 트리의 지름을 찾는 문제이죠. dfs 2번을 돌리면 답을 찾을 수 있다는 것이 증명이 되어있지만, 이번에는 tree dp 로 풀어보았습니다. 과정은 이렇습니다. dfs를 돌리면서 부모-자식 간의 가중치를 return 시켜줍니다. 이때 루트노드까지 도달했을때는 넘겨받은 값들을 vector에 담아줍니다. 그러면 루트로부터 각 리프노드까지 거리가 ..

https://www.acmicpc.net/problem/1231 1231번: 주식왕 동호 첫 줄에는 주식의 개수 C(1 ≤ N ≤ 50)과 주식 매입 및 매각을 할 기간 D(2 ≤ D ≤ 10), 초기 자금 M(1 ≤ M ≤ 200,000)이 공백으로 구분되어 주어진다. 두 번째 줄부터 C+1번째 줄까지 각 줄에는 각각 주 www.acmicpc.net 해설 : 하...졸립지만 이 문제만 해설하고 자겠습니다. 매우매우매우...어려웠던 문제였습니다. ㅠㅠㅠ 먼저 매일 주식을 팔지 안팔지 선택할 수 있습니다. 이 모든 경우의 수를 다해보기엔 많은 시간이 걸리게 되죠. 그럼 이것을 어떻게 잘 최적화를 시켜야 되는데 한번 살펴봅시다. 먼저 오늘 주식이 내려갔는데 팔게된다면 그건 무조건 손해죠. 변동이 없다면? ..

https://www.acmicpc.net/problem/2831 2831번: 댄스 파티 남자 N명과 여자 N명이 상근이가 주최한 댄스 파티에 왔다. 상근이는 모든 사람의 키를 알고있다. 각 남자는 모두 여자와 춤을 출 수 있고, 여자는 남자와 춤을 출 수 있다. 모든 사람은 많아야 한 www.acmicpc.net 해설 : 골드3 인 문제인데 3까지는 아닌 것 같고 4정도면 적당하지 않을까....하는 뇌피셜? 반박시 니 말이 다맞음!!!! 사실 이런문제를 처음 접하게 되면 되게 뜬구름을 잡아야 하는 문제 같게 느껴지게 되기도 합니다. 왜 이렇게 접근하는게 최적인데??라는 물음에 재대로 증명을 할 수 있어야 하지만, 그냥 휴리스틱하게 그렇게 될 것 같아 라는 생각하나만 가지고 접근도 할 수 있어야 하지 않..