Miscellaneous

https://www.acmicpc.net/problem/5569 모든 경우에 대해서 탐색하려고 하면,최대 200C100의 경우의 수가 만들어지므로 시간 안에 해결할 수 없습니다.  해당 문제는 dp로 해결할 수 있습니다.현재칸에 위/왼쪽에서 왔고, 방향을 바꿀 수 있는지에 대한 여부를 기록하기 위해 dp[i][j][k][l]로 표현할 수 있습니다. i, j : 현재 칸의 인덱스k : 0이라면 왼쪽에서, 1이라면 위에서 접근l : 0이라면 방향을 바꿀 수 없고, 1이라면 방향을 바꿀 수 있음    점화식은 위 그림처럼 나타낼 수 있습니다. (파란색, 연두색)빨간색은 {i,j}에 접근하는 모든 경우입니다.이전 칸에서 한번 꺾은(방향을 바꾼) 경우엔 {i,j}에서는 방향을 바꿔선 안되고,반대로 꺾지 않은 경..

https://www.acmicpc.net/problem/24508  나도리를 옮기는 횟수를 최소화하려면, 일단 나도리 수가 작은 바구니부터 나도리를 옮겨 비워야 합니다. (greedy)이를 위해서는 정렬은 불가피함을 쉽게 파악할 수 있었습니다. 여기서 1. 투포인터를 쓰는 풀이와 2. 수학적으로 간단하게 푸는 풀이를 소개합니다.   1. 투포인터 풀이 나도리가 가장 많이 들어있는 바구니부터 채워줍니다. 나도리의 수를 기준으로 오름차순 정렬하여, 가장 앞에 있는 나도리부터 차례대로 가장 뒤에 있는 바구니에 넣습니다. 즉, 현재까지 나도리가 가장 적게 들어있는 바구니에 있는 나도리를 나도리가 가장 많이 들어있는 바구니에 채워넣습니다. 동시에 나도리의 이동 횟수를 기록해줍시다. 나도리를 k개 다 채웠다면, ..

https://www.acmicpc.net/problem/2716      수학 잼병인 작성자인지라... 증명이 옳은지는 모르겠습니다.. 결국 트리의 높이(최대 깊이)를 구하는 것이 문제의 key이므로,입력 string을 읽으면서 트리의 최대 깊이를 구해주기만 하면 되는 문제였습니다.   코드#includeusing namespace std;#define X first#define Y second#define rep(i,x,y) for(int i=x;i pii;typedef pair pll;typedef tuple tiii;int dx[] = { 0,0,1,-1 };int dy[] = { 1,-1,0,0 };/*----------------------*/void solve(){ string s; ..

https://www.acmicpc.net/problem/17353레이지 프로파게이션 공부하다가 만난 문제입니다.그래서 "레이지를 쓰긴 하겠구나"는 알았지만, 어떻게 레이지를 써야될 지가 막막했습니다.도저히 고민해도 풀이가 떠오르지 않았기에, 결국 답을 봤던 문제입니다.. 일단 Lazy Propagation은 기본적으로 두가지 연산을 지원합니다.1. 구간에 대한 단일값 업데이트 쿼리2. 구간에 대한 쿼리 하지만 문제에서 주어지는쿼리는 다음과 같습니다.1. 구간에 대한 다중값(등차수열) 업데이트 쿼리2. 점에 대한 쿼리  우선 구간 업데이트입니다. 문제를 위해 구간에 대해 1,2,3,...,R-L+1씩 업데이트 해야합니다.하지만 가지고있는 연산은 단일 값으로만 업데이트가 가능합니다. 그래서 처음 생각해봤던..

https://www.acmicpc.net/problem/16624  팀원들과 ICPC 골랜디 연습 중에 찾은 문제였습니다.   n개의 5*5 빙고판이 있고, 무승부 즉, 동시에 빙고가 되는 판의 쌍이 존재하는 지 찾는 문제입니다. 여기서, 빙고는 대각선, 세로를 제외한 가로줄만 인정합니다.  가장 먼저 떠올린 풀이는, 빙고판의 숫자가 최대 3000이기 때문에, 가능한 모든 빙고 조합에 대해서 완전탐색하고자 하였습니다. 그렇게 되면, 모든 조합은 3000C5 = 약 2000조...이기때문에 시간 안에 돌기에는 무리가 있습니다. 여기서 n이 100이고, 빙고판은 5*5이므로 모든 빙고판에 중복없이 작성한다면 총 100*5*5 = 2500 가지의 숫자가 적히므로, 줄여도 2500C5 = 약 800조로 마찬가..

https://www.acmicpc.net/problem/18405문제는 간단합니다. n*n 시험관에 바이러스 번호에 번호가 매겨져있고, 번호 순서대로 주변 한칸씩 퍼뜨리는 연산을 s번 돌리는 문제입니다.예를 들어 바이러스가 1,2,3번이 있고, s=3이라면1,2,3, 1,2,3, 1,2,3 순서대로 바이러스를 퍼뜨립니다. 되게 간단한 문제라 이번 포스팅에서는 문제를 푸는 방법보다는 코드를 최적화 하는 방법에 초점을 맞춰서 작성하고자 합니다. 총 9단계를 거쳐서 코드를 개선해나가보겠습니다! 우선 첫번째 코드입니다.#includeusing namespace std;int dx[] = {0,0,1,-1};int dy[] = {1,-1,0,0};int board[202][202];int vis[202][202..

https://www.acmicpc.net/problem/2405  완전탐색으로 돌기에는.. n 우선, 중위값과 평균값의 식을 잘 정리해보았고, 식을 통해 그리디하게 답을 구할 수 있었다.  ta-tb 또는 tc-tb를 최소화하려면 배열을 정렬했을때, 두 원소가 이웃하면되고,반대로 최대화하려면 가장 멀리 떨어져있어야 한다. #includeusing namespace std;#define X first#define Y second#define rep(i,x,y) for(int i=x;i pii;typedef pair pll;typedef tuple tiii;int dx[] = {0,0,1,-1};int dy[] = {1,-1,0,0};/*----------------------*/int main(){ ..

https://www.acmicpc.net/problem/1736  알고리즘 동아리 시간에 고민하다가 결국 못풀었던 문제.처음 고민할땐 DP로 풀릴거같아서 어떻게든 점화식을 세워 보려고 했었는데.. 잘 안되더라;그리고 점화식 고민하면서 DP인것도 의심이 들었던게, 시간제한이 2초나 되고, N,M이 최대 100밖에 안돼서.. 확신이 안섰다..(조금 직접적인) 힌트를 들어도 이해가 안됐다가, 다행히 다음날에 번뜩 아이디어가 떠올라서 풀었더니 AC !  일단, 로봇의 움직임은 문제에서 나왔다시피 아래쪽 또는 오른쪽 둘 중 하나이다.최소의 로봇을 사용하므로, 하나의 로봇이 최대한 많은 쓰레기를 치워야 한다. 따라서 모든 쓰레기를 치우기 위해선, 어떤 로봇은 가장 위, 가장 왼쪽에 위치한 쓰레기에 도달해야하고, ..