Contest for Newbies

팀 블로그에서 옮겨왔습니다.

백준 그룹에 많은 분들이 가입하시고,
또 연습에도 열심히 참가해주셨습니다.👏

확실히 경쟁하는 사람이 많아지니 모두들 의욕을 북돋아 준 것 같습니다!
원래는 스코어보드를 캡쳐해 올렸었는데, 옮기면서 사라졌네요..ㅋ

Ⓐ 직사각형에서 탈출 (1085)

얼핏 보면 케이스를 나누어서 대각선이랑 여러 길이를 구해야 할 것 처럼 보이지만,
사실은 그렇지 않답니다!

직사각형 내부에서 잇는 점이기 때문에 절대적으로 대각선의 길이가 최소인 경우는 존재하지 않아요!

따라서 x축과 평행한 선, y축과 평행한 선으로 가는 수선의 길이만 찾아주면 되겠습니다.

Ⓑ 바이러스 (2606)

그래프 탐색으로 1번 노드를 포함하는 컴포넌트 속 노드의 개수를 묻는 문제입니다.
전형적인 dfs문제인데, 반복적으로 풀어서 구현 속도를 높이는 것이 중요합니다.

Ⓒ 요세푸스 문제 0 (11866)

아니, 저는 이게 실4보다는 높아야 된다고 생각해요..!

동적 배열을 이용해서 푸는 문제인데, STL에 익숙하지 않으신 분들에게는 어려울 수 있거든요. (물론 동적 배열을 이용하지 않는 풀이도 존재할 수 있습니다)

이 문제의 역사 (시간낭비가 싫다면 생략하세용)

요세푸스는 고대 예루살렘의 개천재입니다. (3개국어 능통의 유대인)
옆 나라 로마군에 의해 포위된 상태에서
사람들이 동굴 안으로 피신했고, 결국 가망이 없자...
"적군에게 죽임을 당하거나 포로로 잡힐 바에는 자결을 택하겠소!!!"라고 대동단결을 했습니다.

그러나 요세푸스와 그가 아끼는 자식은... '솔직히 투항해서 살아남는게 맞지 않음?;'이라는 생각을 하게 됩니다.
그래서 요세푸스는 이럽니다.
"아니 솔직히 너네중에 칼로 자기자신을 있는 힘껏 찌를 수 있는 사람이 있다고?"
"고건 좀 에바야;; 우리 그러지 말고 둥글게 서서,"
"어어, 그렇게 너 거기 서고"
"어 아들, 넌 거기 서면 돼."

"이 상태에서 각자 3명 띈 자리 애들을 찔러주세요!"
개천재였던 그는 순식간에 마지막까지 살아남는 두 자리에 지 아들놈과 자신을 끼워넣었다.

그러고서 로마군에게 투항하고, 정보를 다 불어가지고 황제가 로마 시민으로 인정해줍니다.
그래서 그는 로마의 역사가로 지내며 행복하게 오래오래 잘 살았답니다.

문제 요약 및 이해

n명이 있는 상황에서 k명씩 건너뛰면서 없애나갑니다.
만약 선택된 놈들이 사라지지 않고 그 자리에 남아있다면, 그저 나머지 연산을 이용해 풀 수 있었겠죠?
하지만 이 경우에는 선택된 놈들을 제거하기 때문에 1칸씩 줄어들게 되어있습니다.

이 상황에서 선택되는 순서를 출력하라는 것이 이 문제가 요구하는 바입니다.

문제 풀이

1칸씩 줄어들게 되어있습니다.

항상! 1칸씩만 줄어든단 말이죠?
나머지 연산에서 하나씩만 빼주면 되는 거 아닌가요?

• 이 부분은 사소한 +1 -1 차이로 헷갈릴 수 있으므로 직접 종이에 써보시길 권합니다.

그래서, 저 밑에 코드 다 제끼고 핵심만 논하자면,

x가 현재 상황에서 선택한 자리, sz가 현재 상황에서 남은 인원이라 할 때,
$x\, \rightarrow \, x+k$이고, $x+k$가 $sz$밖으로 나간다면, $sz$에 대한 나머지 처리를 합니다.

STL에 대한 이해가 있으시다면 이 설명과 코드를 통해 이해하실 수 있으시리라 믿지만...
댓글로 남겨주시면 부족한 설명 보충해보도록 하겠습니다.

Ⓓ 이진수 덧셈 (1252)

bitset을 활용하면 구현에 드는 시간이 비약적으로 단축됩니다!
bitset은 향후 DP에도 응용되므로 꼭 알아두시길 바래요 ㅎㅎ

Ⓔ 성 지키기 (1236)

도대체 왜 다들 성 지키기를 회피했는지 잘 이해가 가지 않는군요...
성 지키기는 간단한 수학적 사실을 바탕으로 $NGD$ 구현을 우회할 수 있습니다.

문제 풀이

딱 애니팡 생각하시면 됩니다.
혹은 캔디 크러쉬? (더 있으면 댓글로 알려주세요. 오늘 내용중에 제일 중요한 부분이니깐요!)

일단 $idea$는 이겁니다.
놓을 자리의 행 또는 열에 이미 지키고 있는 사람이 있는가?
그렇다면 그 자리에 놓는 것은 정말 의미없는 일이 됩니다. 맞죠?

그래서 행, 열을 사용했는지 여부에 관한 배열을 만들어줍니다.
그리고는 사용되지 않은 행의 수, 사용되지 않은 열의 수 중 더 큰 것을 출력하면 됩니다.

이 부분이 이해가 되실지 안 되실지 잘 감이 안 오네요...
이해가 안되시면 댓글로 남겨주세요!

Ⓕ 단어 공부 (1157)

이거슨...젤 쉬운 문제였어요...
못 푸셨으면 재도전을 추천드립니다.

Ⓖ 하노이 탑 이동 순서 (11729)

하노이탑의 이동 횟수가 $2^n-1$이라는 것은 상식입니다. 이에 대해 궁금하신 분들은 인터넷에 이미 다양한 하노이탑 설명들이 존재하므로 그것들을 보시면 되겠습니다.

하노이탑의 이동 순서는 상당히 직관적입니다.
$n$개를 3번으로 이동시키기 위해서 $n-1$개를 2번으로 이동, 제일 큰 한 놈을 3번으로 이동, $n-1$개를 2번에서 3번으로 이동.

저 부분은 코드로만 구현해내면 됩니다.
지금 1번에서 3번으로 모두를 이동시키는게 목적이고, $n-1$개가 중간에 정차하는 곳이 2번입니다.

그래서, 각각 $s, e, m$이라고 이름을 붙여주면,
$s\rightarrow m$과정, 젤 큰놈에 대해 $s\rightarrow e$과정, $m\rightarrow e$과정을 수행합니다.

그에 대한 코드가 다음과 같습니다.

결국에 그렇게 재귀적으로 나가다보면 $n=1$인 경우를 호출할텐데, 그 때에는 $n-1$이 0이므로 $m$을 거치는 과정을 호출할 것 없이 바로 $s\rightarrow e$ 과정을 출력해주면 됩니다.

Ⓗ 복권 (1359)

식은 맞았는데, combinatinon 처리 과정에서 실수가 생기는 바람에 많이 틀렸습니다.
일단은 식부터 소개할게요.

브론즈인데 조합을 사용해서 좀 놀랐네요.
수학적 내용보다도 알고리즘의 수준이 티어에 반영되기 때문에 생긴 일이라 생각합니다.

저는 여기서 combination의 값이 0이 되는 경우를 제대로 처리하지 않아 왜맞틀을 시전했지만, 여러분은 그러지 않으시길 간절히 바랍니다.

Ⓘ 단축키 지정 (1283)

얘는 저도 못 풀었다는...