https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpFQaAQMDFAUq 1~12월까지의 수영장 이용 계획이 있고 1일, 1달, 3달, 1년 이용권의 요금이 주어질 때, 모든 이용 계획을 커버하는 최소 비용을 구하는 문제이다. 재귀함수를 적절히 설계해서 모든 경우를 찾아서 그 중 최소값을 구하면 된다. go(now,cost) = 현재 위치가 now이고 지금까지 쓴 비용이 cost ans의 초기값을 1년 이용권으로 두고 1. 1일 이용권 사용시 cost에 해당 월 (now) 이용 날짜 * 1일 이용권 사용비용을 더해주고 위치를 1 더한다.2. 1달 이용권 사용시 cost에 1달 이용권 사용비용을 더해주고 ..
https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq 다음 3가지 규칙에 따라 등산로를 만들 때 가장 긴 등산로의 길이를 구하는 문제이다. 1. 등산로는 가장 높은 봉우리에서 시작해야 한다.2. 높은 봉우리에서 동서남북으로 점점 낮아져야 한다. 대각선은 연결할 수 없다.3. 긴 등산로를 만들기 위해 딱 한 곳을 정해서 최대 K 깊이만큼 깎을 수 있다. 우선 가장 높은 봉우리들을 저장하고 DFS 백트래킹으로 각 지점들에서 시작하는 등산로들을 찾아 볼 수 있다. 그렇다면 3번 규칙은 어떻게 고려할 것인가? 경로를 탐색할 때 만약 현재 위치보다 새로운 위치의 높이가 더 낮다면 그냥 가면 된..
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일 때 방문했는가? 큐의 크기만큼 매..
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