The Way
5월 15일 백준 본문
* 코드는 맨 아래에 있습니다
갑자기 머리가 나빠진 것 같다..
<2018 HEPC - PRIME>: 아래 5문제이다. 너무 쉬워서 당황했다.. 초심자용인가
# 백준 15733번: 나는 누구인가
생략
# 백준 15734번: 명장 남정훈
하.. 쪽팔리게 틀린 첫 사람이 되었다. 양발잡이끼리도 남겨줄 수 있다는 것에 주의ㅠㅠ
# 백준 15739번: 매직스퀘어
마방진 문제. 가로, 세로, 대각선을 체크하고 숫자가 한번씩 쓰였는지도 체크해주어야 한다.
사족으로 첫 틀왜맞의 경험이었다. 실수로 세로 체크를 안했는데도 맞았다는...
# 백준 15735번: 삼각
약간 까다로운 문제이다.
나 같은 경우 제대로 된 방향과 뒤집힌 삼각형을 따로 세주었는데,
갯수는 정방향의 경우
(1 + ... + n) + ... + (1 + 2) + (1)
역방향의 경우
(1 + ... + (n - 1)) + (1 + ... + (n - 3)) + ... 이다.
# 백준 15736번: 청기 백기
n 이하의 제곱수의 갯수를 묻는 문제
# 백준 12849번: 본대 산책
다양한 방법이 있겠지만 가장 쉽게 생각할 수 있는 방법은 인접행렬곱일 것이다.
구현하기가 상당히 까다롭다. 여기서 구현해놓은 것을 참고.
# 백준 1697번: 숨바꼭질
몇 가지 알고리즘을 생각해봤었다.
n이 k보다 크거나 같을 때는 뭐 자명하니까.. 넘어가도록 하고
n이 k와 비슷해질때까지 2를 곱한 뒤, 차이를 본다.
예를 들어서 7 차이가 난다면,
(3번 이상 움직였다면) 7 = 8 - 1이므로
끝에서 3번째에 +1을 한 번, 맨 끝에 -1을 한 번 함으로서 k에 도달 가능하다.
그런데 구현이 생각보다 까다로운 것 같아, 폐기처분했다.
그 다음으로, k에서 n으로 탐색하는 것을 생각했다. 구현은 생각보다 간단하다.
이런 걸 백트래킹이라 부른다고 한다. 모든 가능성을 시도하는 알고리즘이라 생각하면 될 것 같다.
1697.cpp