BFS 문제입니다. F층의 높이의 빌딩에서 강호는 S층에 있습니다. 강호가 G층까지 가려고 할 때 U칸 올라가는 엘리베이터 버튼과 D칸 내려가는 엘리베이터 버튼을 몇번 눌러서 도착할 수 있는지 구하는 문제입니다. BFS를 사용해서 현재위치에서 올라가는 경우, 내려가는 경우를 전부 구합니다. 이미 방문한 곳들은 visit처리를 해줍니다. 그리고 visit에는 몇번째 이동인지에 대한 값도 넣어줍니다. G층에 도착하면 visit[G]를 출력하고 더 이상 갈 곳이 없다면 use the stairs를 출력합니다. #include #include #include #include #include using namespace std; int F, S, G, U, D; int visit[1000010]; void BFS..
정렬 문제입니다. 각 인원들이 하나의 ATM기계를 사용하기위해 최단으로 기다리는 총 시간을 구하는 문제입니다. 오래걸리지 않는 사람 먼저 하기위해서 sort함수를 사용해서 정렬했습니다. num은 현재 사람이 걸리는 시간입니다. total은 지금까지 걸린 총 시간입니다. 첫번째 사람이 걸린시간을 num에 추가하고 num을 total에 추가합니다. 두번째 사람이 걸린시간을 num에 추가하고 num을 total에 추가합니다. .... #include #include #include #include #include using namespace std; int main(int argc, char *argv[]) { int n; int num = 0; int total = 0; vector v; cin >> n; ..
xxxx년 1월 1일 ~ xxxx년 yy월 zz일의 총 일 수를 구하는 문제입니다. 고려해야하는 사항은 윤년입니다. 윤년은 4로 나누어 떨어지며 100으로 나누어 떨어지면 안되지만 400으로 나누어떨어지면 괜찮습니다. 이를 코드로 나타내면 다음과 같습니다. if (year % 4 == 0 && (year % 100 != 0 || year % 400 == 0)) 윤년일 경우 3월이 넘는 달을 입력하면 +1을 해줍니다. month의 경우 12개의 배열을 만들어 yy달이 될때까지 배열의 값을 총 일수에 더해줍니다. int mArr[12] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30 }; for(int i=0; i> day; cin >> month; cin >> ye..
기차역 4개에서 사람들이 타고 내릴 때 가장 많은 사람이 기차에 타고 있는 경우의 사람 수를 출력하는 문제입니다. 점화식을 세워서 풀었습니다. arr[i][2] = arr[i - 1][2] + arr[i][1] - arr[i][0]; 현재역의 사람 수 = 이전 역의 사람 수 + 이번 역에서 탄 사람 수 - 이번 역에서 내린 사람 수 입니다. 그리고 현재역의 사람 수들 중 가장 큰 값을 저장해두어서 마지막에 출력했습니다. #include #include #include #include using namespace std; int main(int argc, char *argv[]) { int arr[5][3]; int maxPeople = -1; memset(arr, 0, sizeof(arr)); for (..
숫자를 전부 같게하려고 할 때 최소 몇번 바꾸면 되는지 찾는 문제입니다. 0을 1로 뒤집을 때는 뒤집으려는 0과 인접한 모든 0을 같이 뒤집을 수 있습니다. 1에서 0으로도 마찬가지입니다. 0의 더미들의 개수를 찾고 1의 더미들의 개수를 찾습니다. 그리고 더미의 수가 적은 것들을 뒤집으면 문제를 해결할 수 있기에 min함수를 통해 작은 값을 추출해서 출력했습니다. #include #include #include #include #include using namespace std; int main(int argc, char *argv[]) { string s; int flag; int i = 0; int zero = 0; int one = 0; cin >> s; flag = -1; for (int j = ..
그리디 알고리즘 문제입니다. 1000원을 냈을 때, 물건값이 n이면 1000 - n을 거슬러줘야합니다. 이 때 동전을 가장 적게 거슬러준 값을 출력하는 문제입니다. 500원 보다 크면 거슬러줘야 되는 돈 - 500을 하고 카운트를 증가했습니다. 100원 보다 크면 .... 50원 보다 크면 .... .... 이와 같은 방식으로 500원에서 거르고, 100원에서 거르고, .....를 통해 가장 큰 금액 부터 줄여나가면서 카운트를 해서 최소 횟수를 구할 수 있었습니다. #include using namespace std; int main(int argc, char *argv[]) { int n; int count = 0; cin >> n; n = 1000 - n; while (1) { if (n == 0) ..
다이나믹 프로그래밍으로 문제를 풀었습니다. 점화식은 다음과 같습니다. DP[i] = DP[i - 1] + DP[i - 2]; 현재 위치의 값은 이전과, 그 이전의 값을 더한 값입니다. 이를 반복해서 n의 위치에 피보나치 수를 구할 수 있습니다. #include #include using namespace std; int main(int argc, char *argv[]) { int n; long long DP[45]; cin >> n; DP[0] = 0; DP[1] = 1; for (int i = 2; i
세수를 입력받고 곱셈과 나눗셈을 하나씩 이용하여서 나올 수 있는 가장 큰 값을 출력하는 문제입니다. x * y / z와 x / y * z를 비교해서 큰값을 출력해주었습니다. #include #include using namespace std; int main(int argc, char *argv[]) { double x, y, z; double num1, num2; cin >> x; cin >> y; cin >> z; num1 = x * y / z; num2 = x / y * z; cout