https://www.acmicpc.net/problem/12026 d[i] = i까지 오는데 필요한 에너지 양의 최소값 이라고 하자. 매번 0~i-1까지 검사하면서 현재 알파벳 이전에 올 수 있는 알파벳을 찾아서 최소값을 갱신한다. O(N^2)으로 해결할 수 있다. 123456789101112131415161718#include #include #define INF 987654321using namespace std; int main(){ int n,d[1005]; char s[1005]; scanf("%d %s",&n,s); fill_n(d,1005,INF); d[0]=0; for(int i=1;i
https://www.acmicpc.net/problem/1107 현재 채널이 100이고 리모컨의 버튼을 눌러서 채널 N으로 이동하려고 한다. 리모컨에 고장난 버튼이 있을 수 있다. 이 때 버튼을 최소 몇 번 눌러야 하는지 구하는 문제이다. 최소로 버튼을 누르려면 N과 최대한 가까운 채널을 숫자만 눌러서 이동한 후 나머지 차를 +나 -버튼을 이용해서 이동하면 된다. 먼저 ans을 N과 100의 절대값 차(+나 -로만 이동하는 경우)로 둔다. 그리고 N보다 큰 채널로 이동하는 경우, 작은 채널로 이동하는 경우 각각에 대하여 ans보다 작으면 갱신해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637#include int min(i..
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일 때 방문했는가? 큐의 크기만큼 매..
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..