Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- flutter #app #취준
- flutter #깃
- 로컬저장소 #이름변경
- 백준
- flutter #플러터
- firebase #파이어베이스
- boj #baekjoon #c++
- git #unity #깃허브
- 비주얼 스튜디오 #vs #visual studio
- Flutter
- unity #2d-game
- flutter #firebase #플러터 #파이어베이스 #연동
- flutter #todolist
- flutter #플러터 #분석
- 백준 #boj #baekjoon
- 인턴 #프론트엔드 #개발자 #프론트엔드개발자 #취준
- flutter #git
- 플러터 #flutter #restful #rest api
- 비주얼스튜디오 #코드스니펫
- boj #c++
- flutter #상태관리
- unity #2d-game #minigame #vscode
- baekjoon #boj #c++
- VS #비주얼스튜디오
- 백준 #boj
- #유데미 #udemy #웅진씽크빅 #스나이퍼팩토리 #인사이드아웃 #미래내일일경험 #프로젝트캠프 #부트캠프 #react #리액트프로젝트 #프론트엔드개발자양성과정 #개발자교육과정
- boj #baekjoon
- baekjoon #백준 #boj
- 백준 #c++
- 유데미 #udemy #웅진씽크빅 #스나이퍼팩토리 #인사이드아웃 #미래내일일경험 #프로젝트캠프 #부트캠프 #react #리액트프로젝트 #프론트엔드개발자양성과정 #개발자교육과
Archives
- Today
- Total
cococo-coding
[C++ 풀이] 11034. 캥거루 세마리2 본문
문제 분석
캥거루의 위치 a,b,c를 입력받고 양 끝의 캥거루만을 움직이면서 사이를 좁혀나가는 문제이다.
이때 a와 b사이의 위치, b와 c사이의 위치를 비교하여 더 긴 쪽으로 캥거루를 옮겨야 움직이는 횟수를 최대로 늘릴 수 있다.
알고리즘 설계
움직이는 횟수를 구하는 것이 목표이므로
a와 b, b와 c사이의 더 긴 거리를 구하면 끝이다.
그 거리내에서만 캥거루들을 움직일 수 있기 때문에 -1을 해준 값을 출력한다.
ex)
a:3 b:5 c:9
a나 c캥거루가 캥거루 사이 좌표로 움직여야하므로, a가 b와 c사이로 뛰어간다.
이때 최대횟수로 만들어야하므로 a는 8로 움직인다.
이후로는 c가 다시 7로 움직이고, 다시 a가 6으로 움직이고 ...
이런 식으로 반복이 되므로
결국은 처음에 주어진 좌표에서 긴 거리를 구하면 끝이다.
시간 복잡도
while문으로 입력받는 값에 따라 달라짐
코드
#include <iostream>
using namespace std;
/*
1. 캥거루의 초기 위치 abc를 받는다
2. 각 케이스별로 최대 움직임 횟수를 구한다.
*/
int main() {
//1
int a, b, c;
//2
while (cin >> a >> b >> c) {
cout << max(b - a, c - b) - 1 << '\n';
}
return 0;
}
느낀 점
문제를 손으로 풀어보면서, 캥거루가 뛸 때마다 바뀌는 좌표도 다 입력을 해야하나? 라는 생각이 들어 굉장히 복잡한 알고리즘을 짜야겠다고 생각이 들었다.
그러나 계산해본 결과 어차피 긴 거리를 선택하면, 그 거리 내에서만 움직이는 게 끝이기 때문에 주어진 거리 중 큰값을 max()함수로 구해서 1을 빼준 거리를 출력하면 된다.
'[BOJ] 코드 모음 > C++_알고리즘' 카테고리의 다른 글
1789번. 수들의 합 (1) | 2024.02.06 |
---|---|
15786번. Send me the money (1) | 2024.02.06 |
[C++ 풀이] 14659번. 한조서열정리하고옴ㅋㅋ (0) | 2024.02.01 |
[C++ 풀이] 2810번. 컵홀더 (1) | 2024.01.30 |
[C++ 풀이] 2864번. 5와 6의 차이 (0) | 2024.01.28 |