https://www.acmicpc.net/problem/2138 첫번째 위치의 스위치를 누르거나 안 누르는 두 가지 경우에 대하여 최종 원하는 상태의 전구와 비교하여 그리디하게 끝까지 상태를 확정해나간다. 그리고 끝부분에서 스위치를 누르거나 안 누르는 두 가지 경우에 대하여 최종 상태를 만들 수 있는지 살펴보면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940#include #include #include #define INF 100001using namespace std; int n,ans=INF;string s1,s2,e; void go(string& s,int now,int cnt){ if(now==n-1) { ..
https://www.acmicpc.net/problem/2573 지구온난화로 인하여 북극의 빙산이 녹고 있다. 1년이 지날 때마다 빙산의 각 칸은 인접한 바다의 칸의 개수만큼 녹는다. 이 때 최초로 빙산이 2개로 나눠지는 시점을 구하는 문제이다. 매 시점마다 DFS로 섬의 개수를 세주고 2개 이상이면 루프를 탈출하고 답을 출력한다. 아직 빙산이 분리되지 않았다면 water 함수를 통해 빙산의 각 칸마다 인접한 바다의 개수를 구해서 저장해놓고 빙산의 상태를 갱신한다. 이 때 2개로 나눠지기 전에 모두 바다로 변한다면 0을 출력한다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253..
https://www.acmicpc.net/problem/9019 정수 A에서 D,S,L,R 연산을 쓰면서 정수 B를 만드려고 할 때 최소 연산 횟수를 구하는 문제이다. BFS로 구할 수 있다. 큐에 (int 정수,string 지금까지 쓴 명령어)를 넣으면서 답을 찾는다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485#include #include #include #include #include using namespace std; int a,b;bool visit..
https://www.acmicpc.net/problem/1600 원숭이가 격자판의 왼쪽 맨 위에서 오른쪽 맨 아래로 이동하려고 한다. 이동하는 방법은 두 가지가 있다. 일반적인 동서남북 이동과 체스에서의 말의 이동이다. 말의 이동은 최대 K번 까지 할 수 있다. 이 때, 목적지까지 갈 수 없다면 -1를 출력하고 아니면 이동 횟수의 최소값을 출력하는 문제이다. 일반적인 BFS에서의 이동과는 다르게 말의 이동이 추가되어 있다. 그리고 이동할 때마다 말의 이동 가능 횟수가 줄어든다. 현재 위치에서의 남은 말의 이동 가능 횟수가 다르면 다른 상태로 보고 visit 배열을 3차원으로 선언해준다. visit[x][y][k] = 현재위치가 (x,y)이고 남은 말의 이동 횟수가 k일 때 방문했는가? 큐의 크기만큼 매..
http://codeforces.com/contest/931/problem/B 2^k개의 팀이 각각 순서대로 1~2^k로 팀번호가 정해지고 토너먼트를 한다. 이 때 주어진 a,b팀이 몇번째 라운드에서 만나는지 구하는 문제이다. 결승전에서 만나면 "Final!"을 출력한다. 각 팀을 0부터 indexing해서 a,b를 2로 나누면 다음 라운드의 몇번째 팀인지 알 수 있다. 나눌 때마다 라운드가 증가되고 팀이 절반으로 줄어든다. 이 때 a와 b가 같아지는 시점이 두 팀이 만나는 라운드가 된다. 이 때 팀이 하나라면 결승전이다. 123456789101112#include int main(){ int n,a,b,r=0; scanf("%d %d %d",&n,&a,&b); a--,b--; while(a!=b) a/..
http://codeforces.com/contest/931/problem/A 좌표 상에 친구 두 명이 서 있다. 각각 한 좌표씩 이동할 때마다 피로도가 1,2,3 ... 순차적으로 증가한다. 이 때 두 사람의 피로도의 합을 최소로 하면서 만나는 경우에 그 합을 구하는 문제이다. 두 사람의 좌표의 차에서 절반씩 이동하면 된다. 123456789101112#include int main(){ int a,b,d; scanf("%d %d",&a,&b); d=a-b; if(d
https://www.acmicpc.net/problem/11444 F[2n-1] = F[n]^2+F[n-1]^2F[2n] = (F[n-1]+F[n+1])*F[n] = (2*F[n-1]+F[n])*F[n] 위의 두 점화식을 이용하여 메모이제이션을 한다. 1234567891011121314151617181920212223242526272829303132333435#include #include using namespace std;typedef long long ll; map d;ll mod=1000000007; ll f(ll n){ if(n0) return d[n]; if(n%2) { ll m=(n+1)/2,a=f(m),b=f(m-1); d[n]=(a*a+b*b)%mod; return d[n]; } els..
https://www.acmicpc.net/problem/9935 문자열과 폭발 문자열이 주어졌을 때 모든 폭발이 끝났을 때의 문자열의 상태를 출력하는 문제이다. 2개의 스택 st, temp을 둔다. 문자열을 쭉 스캔하면서 폭발 문자열의 끝과 서로 같지 않거나 st의 크기가 폭발 문자열의 크기보다 작을 때는 그냥 st에 넣어준다. 그러다가 폭발 문자열의 끝과 같은 시점에서 st에서 하나씩 빼서 temp 옮기면서 폭발 문자열 전체와 같은지 확인한다. 만약 같다면 다 옮긴 후 temp에서 없애주고 중간에 같지 않다면 다시 st로 옮겨준다. 최종으로 st에 남은 문자열이 정답이다. 스택에 역순으로 저장되어 있으므로 temp에 다 옮긴후 하나씩 빼면서 출력해주면 된다. 12345678910111213141516..
https://www.acmicpc.net/problem/1406 에디터를 구현하는 문제이다. 배열로 구현하면 삽입이나 삭제 연산이 O(N)이 걸리므로 스택이나 연결리스트를 이용해서 O(1)만에 삽입과 삭제가 가능하게 한다. 스택으로 구현시 커서를 기준으로 왼쪽, 오른쪽 두 개의 스택을 두고 구현한다. 스택 이용 1234567891011121314151617181920212223#include #include using namespace std; int main(){ stack l,r; char c,a; while((c=getchar())!='\n') l.push(c); int n; scanf("%d",&n); while(n--) { scanf(" %c",&c); if(c=='L' && !l.empty(..