본문 바로가기

Problem Solving

(55)
[BOJ] 20093 Coins 문제 설명 $8 \times 8$ 크기의 체스보드가 있습니다. $A$와 $B$가 이 위에서 게임을 합니다. 각 체스보드에는 동전이 하나씩 올려져 있고, 처음 상태는 무작위입니다. $A$는 동전을 최대 한 개 뒤집어서, $0$ 이상 $63$ 이하의 정수 하나를 체스보드만 보고 $B$가 알 수 있게끔 해야 합니다. $A$와 $B$의 전략을 직접 구현해 제출하는 투 스텝 문제입니다. 문제 관찰 서브태스크 1 동전을 하나 뒤집을 수 있다는 건, 원하는 위치의 동전을 위 또는 아래로 정확히 맞출 수 있다는 것과 동치입니다. 따라서 0번 위치의 동전을 잘 뒤집어 주면 됩니다. 서브태스크 4 서브태스크 1과 비슷한 느낌으로 접근합시다. $A$가 $B$에게 전달해야 하는 정보는 정확히 6비트어치입니다. 따라서 6개의 ..
[BOJ] 19677 Holy cow, Vim! (Hard) 문제 설명 생략한다. 문제 접근 이 문제를 풀기 위해서는 굉장히 많은 시행착오를 거쳐야 한다. 아래는 그 시행착오를 줄이기 위한 접근들을 단계별로 서술해놓았다. 그러나 이를 보지 않고 많은 시행착오를 겪는 것이 거의 모든 측면에서 도움이 될 것으로 보인다. 일단 lexicographical하게 정렬했을 때 명령어의 순서는 '*', '+', '-', '/', 'dup', 'input', 'jump', 'pop', 'print', 'push' 순서이다. 문제는 이 중 사칙연산과 dup은 우선순위도 빠르면서 스택에 필수적으로 하나 이상의 원소를 요구하기에, 두 명령어 ..
정보올림피아드 / 알고리즘 과외 안 구합니다. 알고리즘 과외 안 합니다 현재 고려대학교 컴퓨터학과 재학 중인 김준겸입니다. 알고리즘 사이트에서는 ryute라는 닉네임을 사용 중입니다. 약 8년 정도의 알고리즘 문제 해결 경력이 있습니다. 알고리즘, 그 중에서도 특히 정보올림피아드 분야 과외를 하고자 합니다. Zoom과 Visual Studio Live를 통한 화상 과외를 주로 받습니다. 모든 세부사항은 상담을 통해 조정이 가능하니, 부담 갖지 마시고 연락 주시길 바랍니다. 코딩 테스트 수준의 과외는 별도의 특이사항이 없는 한 당분간 받지 않으려고 합니다. 연락을 많이 주시는데 받지 못해 죄송합니다. 새로 이메일 주시면 과외 다시 진행하게 될 때 먼저 연락드리겠습니다. 당분간 과외를 받지 않습니다. 어떤 일이 있어도 과외를 해야겠다 싶은 경우에만 연락..
USACO 2020 Open contest Gold 풀이 Intro PS를 거의 한달간 접었었는데, 올해 ICPC를 나갈 수 있다는 희망이 보여서 급하게 PS 재활 중입니다. 최대한 빨리 플래티넘을 안정적으로 해결할 수 있는 실력까지 올렸으면 좋겠네요. 가능할지는 아직 미지수입니다. 이 셋 푸는데도 두시간은 넘게 걸렸으니 미래가 어둡네요 :( 18874 Haircut 문제 링크 : https://www.acmicpc.net/problem/18874 문제를 요약하면 각 $j$에 대해 $j$보다 큰 수열의 원소들이 정확히 $j$로 바뀔 때, 수열의 inversion을 구하는 문제입니다. 이런 문제에서 흔히 나오듯이 $j$를 큰 수부터 작은 수까지 움직이면서 차례대로 구해봅시다. 수열의 inversion은 수열의 각 원소 $a_i$에 대해 인덱스가 $i$보다 작으면..
(임시) 2020 ICPC Seoul Regional 후기 * 페이스북에 올린 것을 급하게 그대로 올립니다. 14일날 있었던 Seoul Regional과, 그리고 리저널을 치기 위해서 노력했던 시간들에 대해 짧은 후기글을 올립니다. (긴 후기는 나중에 블로그에 올라올 것 같습니다.) 두서가 좀 없어도 이해해 주세요. 저희 팀은 결성된 지 상당히 오래 된 팀입니다. 올해 1월에 만들어졌고, 그때부터 팀연습을 몇 번 했던 것 보면 태생이 빡겜을 하기 위해 만들어진 팀이었던 것 같습니다. 저 또한 재수하려고 마음을 먹었다가 이 팀 구성이면 Semi-World Final에는 무조건 진출하겠다고 생각이 들어서 재수를 포기하고 PS를 계속 했습니다. 결과적으로 좋은 성적을 냈으니 옳은 선택이었다고 생각합니다. 사실 저희 팀이 객관적으로 잘하는 팀이다 말하기는 아직도 힘들다..
Random Problem Solving 1 Intro 정말 PS를 하고 싶었기 때문에, 몇 문제를 풀었다. 잘 푼 문제도 있고 그렇지 못한 문제도 있지만, 어쨌던 간에 풀었던 문제들의 기록을 간단하게나마 남길까 한다. 20045 Trading System 먼저 다음과 같은 값을 찾는다. 구간합이 $x$ 이상인 구간의 개수가 $k$ 이상인 가장 큰 $x$ 이 값을 찾아야 하는 이유는, 이 값을 찾는다면 실제 수열은 $x+1$ 이상인 구간합을 모두 set을 이용해서 찾아 준 다음 나머지를 $x$로 채우는 방식으로 역추적해낼 수 있기 때문이다. 따라서 이 값을 찾는 것이 답을 구하는 것과 동치이고, 이 정도 문제를 해결할 수준이라면 이 과정은 매우 쉬우므로 설명은 생략할 것이다. 이 값은 $x$에 대한 Parametric Search로 찾아줄 수 있다..
[BOJ] 17524 Dryer 문제 링크 : www.acmicpc.net/problem/17524 문제 풀이 가장 먼저 해야 하는 관찰은 다음과 같다. $t_i$가 같은 옷이 2개 있다면 어차피 $w_i$가 큰 쪽이 더 오래 걸릴 것이기 때문에, 같이 넣고 말려도 무방하다. 따라서 의미 있는 옷은 각 $t_i$에 대해서 유일하므로, $1\le N\le61$과 사실상 같다. 그 다음으로 해야 하는 관찰들은 다음과 같다. 어떤 옷들의 집합을 같은 건조기에 넣고 돌린다면, 그 건조기의 온도는 반드시 옷 중 $t_i$의 최솟값과 같아야 한다. 이는 매우 자명하다. 어떤 건조기가 이미 $x$초 동안 돌아간다면, $x$초 이하를 소모하는 다른 옷을 끼워 넣어도 상관없다. $k=3$일때만 해결하면 그 아래는 쉽게 해결할 수 있으므로 이 경우에 대..
[SCPC] 2020 1차 예선 풀이 Intro대충 4시간 정도 때려 박아서 1~4번에서 만점을 받았고, 5번은 문제만 읽었습니다. 예전 SCPC 기출에 비해서는 확실히 난이도가 균일해진 것 같습니다(https://newdeal123.tistory.com/61 참조 요망). 제가 예상하는 Solved.ac 티어 난이도는 다음과 같습니다.다이어트 (Silver 3)카드 게임 (Platinum 3)사다리 게임 (Platinum 3)범위 안의 숫자 (Platinum 2)우범 지역 (Diamond 2~3?)1. 다이어트다음과 같이 생각해봅시다. 일단 자명히 두 식단에서 칼로리가 낮은 순으로 K개만 먹어야 한다는 것을 알 수 있습니다. 이때 식단 A의 가장 큰 칼로리를 가지는 식사는 B의 어떤 식사랑 매칭시켜야 할까요? 당연히 B의 가장 작은 칼로리..