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

https://www.acmicpc.net/problem/1052 1052번: 물병 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번 www.acmicpc.net 정말 오랜만에 포스팅 합니다. 맥북에어를 사고 첫 포스팅인데 사실 그동안 글쓰는 것에 대해 많은 고민이 있어서 생각좀 정리하고 다른 바쁜일도 생겨서 어쩌다가 오랜만에 글을 올립니다. 해설 : 먼저 처음에 큐를 사용해서 풀면 되겠지 했습니다. priority queue 를 선언한 후 하나빼고 top에 있는 아이 비교해서 동일하면 다시 pop 해서 1더해주고 집어 넣고,,,근데 우리가 코딩을 하다보면 이건..

https://www.acmicpc.net/problem/15659 15659번: 연산자 끼워넣기 (3) 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 먼저 이 밑에 두 문제를 안푸신 상태라면 풀고 오시는 걸 추천드립니다. https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 ..

https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 해설 : 대표적인 백트래킹 문제입니다. 모든 칸들을 확인하면서 만약 0 이 아니라면 다음칸으로 넘어가고, 0이면 1~9까지 전부 대입해 보면서 현재 스토쿠 규정에 어긋나는지 아닌지를 확인해 보면되겠죠. 살짝 버벅거리는 부분은 y 가 8번째 일때는 다음 줄로 넘어가서 (x+1,0) 부터 시작해야 할텐데 이걸 어떻게 해주지? 라는 생각이 들수 있을 텐데 이는 'dfs(x + (y == 8), (..

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 <..