맛있는감귤

문제 : https://www.acmicpc.net/problem/1890출처Olympiad > Baltic Olympiad in Informatics > BOI 2006 6번 DP로 해결가능한 문제다. 0,0에 1을 넣고 반목문을 돌면서 오른쪽, 아래로 이동 가능한 곳의 값을 더해준다. (dp값은 그 좌표에 도달 가능한 루트의 개수이다.) 유의할 점은 jump값을 더할 때 N의 값을 초과하지 않는지, N-1, N-1 은 연산을 제외 했는지, 경로의 개수를 고려했는지 이 정도 되겠다. 경로의 개수가 많아 BFS로 풀게 되면 메모리 초과가 나오지 않을까 싶다. #include int N; int map[101][101]; long dp[101][101]={0,}; bool visited[101][101];..

문제 : https://www.acmicpc.net/problem/5397 커서를 이동하며 문자를 삽입하거나 지워야하는 문제는 앵간하면 스택이나 큐로 풀 수 있다. 처음에는 리스트를 생각했지만 iterator로 복잡하게 할 바엔 stack이 나을 것 같아서 stack으로 해결했다. 쉽다고 생각하고 막 풀다가 testcase가 바뀌는 시점에서 줄바꿈을 안하는 멍청한 실수를 했다. #include &ltiostream&gt #include &ltstring&gt #include &ltstack&gt using namespace std; stack&ltchar&gt s1,s2; int T; int main(){ cin&gt&gtT; while(T--){ string s; cin&gt&gts; for(int i..

문제 : https://www.acmicpc.net/problem/9019출처ACM-ICPC > Regionals > Asia > Korea > Nationwide Internet Competition > Asia Regional - Daejeon Nationalwide Internet Competition 2011 D번횟수가 아닌 연산의 순서를 출력하는 BFS 문제.그냥 queue 으로 풀었다.100이라는 숫자가 L을 했을 때 1000이되어야하는지 1이 되어야하는지 헷갈려서 두 방식으로 다 풀어봤는데 1000이 되는게 맞았다.4636 MS 나온건 함정 #include #include #include using namespace std; int main(){ int T; cin>>T; while(T--)..

문제 : https://www.acmicpc.net/problem/5427출처ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2012 F번 일반적인 미로찾기에서 퍼져나가는 장애물이 추가된 문제다. 미로찾기 + 바이러스 라고 생각하면 된다.시간을 따로 관리했다면 3차원 배열로 풀었을텐데 일괄적으로 관리해서 2차원으로 해결했다.먼저 불이 번지는 것을 연산하고 이동을 했다. 어처피 현재 위치는 큐에 들어있기 때문에 불이 먼져 번져도 상관없음비슷한 문제 : https://www.acmicpc.net/problem/3055 #include #includ..

문제 : https://www.acmicpc.net/problem/1963출처ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2006 G번 최소 횟수를 구한다는 점에서 BFS를 이용해 풀 수 있다는 것을 유추할 수 있다. 이 문제의 핵심은 기존의 숫자를 한 자리씩 바꾸는 것과 소수판별이다. 제출횟수 대비 정답률이 굉장히 높은게 신기하다. #include &ltiostream&gt #include &ltqueue&gt using namespace std; bool nextPrime(int n){ if( (n&1) == 0 ) return (n == 2); for(int i=3; i*i&lt=n; i++) { if(..

문제 : https://www.acmicpc.net/problem/5014출처ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > Nordic Collegiate Programming Contest > NCPC 2011 D번 1차원 BFS 문제, 주어진 U,D에 따라 상하 이동만 있다고 생각하면 된다. #include #include using namespace std; bool visited[1000001]; queue q; int main(){ int F,S,G,U,D,cnt=0; bool flag = false; cin>>F>>S>>G>>U>>D; visited[S]=true; q.push(S); while(!q.empty..

문제 : https://www.acmicpc.net/problem/2573 시간에 따라 맵이 바뀌는 문제이다. 얼음이 녹을 때 시간마다 -1인줄 알았는데 기준점에서 동서남북 상태에 따라 얼음 융해도가 다르다는 것을 간과한 것이 문제였다. 코드가 더럽게 되었는데 문제점이 있으면 댓글로 지적해주시면 감사하겠습니다. #include &ltstdio.h&gt int R,C,cnt=0,time=0; int map[303][303]; bool isVisited[303][303]; int dr[4]={1,-1,0,0}; int dc[4]={0,0,1,-1}; void dfs(int r,int c){ isVisited[r][c] = true; for(int i=0;i&lt4;i++){ int nr = r+dr[i], ..

문제 : https://www.acmicpc.net/problem/2468출처Olympiad > 한국정보올림피아드 > KOI 2010 > 초등부 2번DFS 문제입니다. 잠기는 높이가 0일 때도 포함되는 것을 유념하시길 바랍니다.반복문 인자로 자주 쓰는 i,j,k는 함수 파라미터로 사용하지 말자...ㅠㅠ #include int map[101][101],ans=0,N; int di[4]={1,-1,0,0}; int dj[4]={0,0,1,-1}; bool isVisited[101][101]; void dfs(int ii, int jj, int k, int cnt){ isVisited[ii][jj] = true; for(int i=0;i= 0 && nj >= 0 && ni < N && nj < N && map..

문제 : https://www.acmicpc.net/problem/12790출처Contest > Coder's High > Coder's high 2016 Round 1: Online A번 MP는 5 * MP니깐 1 미만일 경우 1 * 5가 되어야 한다. #include &ltstdio.h&gt int main(){ int T; scanf("%d",&T); while(T--){ int hp=0,mp=0,a=0,d=0,n[8]; for(int i=0; i

문제 : https://www.acmicpc.net/problem/2477 github : https://github.com/JEONG-SEUNGWOOK/BOJ/blob/master/2477.cpp 출처 Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2010 > 초등부 3번 Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2010 > 중등부 2번 가장 긴 width와 height 값의 곱이 전체 사각형 넓이가 되고 양 옆의 테두리가 평행하다면 그 가운데에 놓인 테두리가 작은 사각형을 이루는 테두리다. 그 값 계산해 빼주면 전체 넓이가 나온다. #include #include using namespace std; struct Length{ int l=0, d=0; }; int..