문제 링크입니다: www.acmicpc.net/problem/16431
16431번: 베시와 데이지
베시는 (3, 5) > (2, 4) > (2, 3) 경로로 이동하여 존에게 오는데 2초가 걸립니다. 반면 데이지는 (1, 1) > (1, 2) > (1, 3) > (2, 3) 경로로 이동하여 존에게 오는데 3초가 걸리므로 베시가 더 빨리 도착합니다.
www.acmicpc.net
처음 문제를 봤을 때는 BFS로 접근하려고 했는데, 수학적으로 간단하게 풀 수 있는 문제였습니다.
칸과 베시의 가로 좌표 길이 차를 r, 세로 좌표 길이 차를 c로 지정하고 r > c라고 가정했을 때, 베시는 대각선으로 움직일 수 있으므로 max(r, c) - min(r, c)만큼 대각선으로 움직이고 min(r, c)만큼 세로로 움직이면 됩니다. 따라서, 베시가 도착하는 속도는 max(r, c)입니다.
반면 데이지는 상하좌우로만 움직일 수 있으므로 도착하는 속도는 r + c 입니다.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <algorithm> | |
using namespace std; | |
typedef struct | |
{ | |
int r, c; | |
}Coord; | |
int main(void) | |
{ | |
ios_base::sync_with_stdio(0); | |
cin.tie(0); | |
Coord bessie, daisy, kahn; | |
cin >> bessie.r >> bessie.c >> daisy.r >> daisy.c >> kahn.r >> kahn.c; | |
int bessieDuration = max(abs(kahn.r - bessie.r), abs(kahn.c - bessie.c)); | |
int daisyDuration = abs(kahn.r - daisy.r) + abs(kahn.c - daisy.c); | |
if (bessieDuration > daisyDuration) | |
{ | |
cout << "daisy\n"; | |
} | |
else if (bessieDuration == daisyDuration) | |
{ | |
cout << "tie\n"; | |
} | |
else | |
{ | |
cout << "bessie\n"; | |
} | |
return 0; | |
} |


개발환경:Visual Studio 2017
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
반응형
'알고리즘 > BOJ' 카테고리의 다른 글
백준 16600번 Contemporary Art (0) | 2021.03.24 |
---|---|
백준 16486번 운동장 한 바퀴 (0) | 2021.03.24 |
백준 16199번 나이 계산하기 (0) | 2021.03.23 |
백준 16017번 Telemarketer or not? (0) | 2021.03.23 |
백준 15963번 CASIO (0) | 2021.03.23 |