kth990303의 코딩 블로그

스터디그룹에서 연습 C번으로 진행된 문제. 어떻게 보면 되게 쉽지만, 어떻게 보면 마냥 쉽지만은 않은 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/14867 14867번: 물통 표준 입력으로 물통 A의 용량을 나타내는 정수 a(1 ≤ a < 100,000), 물통 B의 용량을 나타내는 정수 b(a < b ≤ 100,000), 최종 상태에서 물통 A에 남겨야 하는 물의 용량을 나타내는 정수 c(0 ≤ c ≤ a), 최 www.acmicpc.net 의식의 흐름 및 해설 물통 물 양이 각각 C, D가 되기 위한 최소 횟수를 구하는 문제. 이런 유형은 보통 BFS로 접근하는데, 문제는 N이 최대 10만이라 이차원배열로 방문체크를 하면 무조건 시간초과 혹은 메모리초과가 난..

*주의* 정해와 다르게 해결하였으며, 정해 풀이는 올리지 않습니다. 스터디그룹 연습에서 B번으로 나온 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/3980 3980번: 선발 명단 각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 한 줄에 하나씩 출력한다. 항상 하나 이상의 올바른 라인업을 만들 수 있다. www.acmicpc.net 의식의 흐름 및 해설 문제 이해가 조금 힘든데, 쉽게 풀이하자면 모든 포지션에 한 명 이상의 선수가 위치해야 된다. 모든 포지션에 선수가 위치해야 되므로 TSP와 똑같다. 그러므로 이 문제와 거의 유사하다. https://kth990303.tistory.com/61 [BOJ] 백준 1311. 할 ..

스터디그룹에서 진행한 연습 중 A번으로 나왔던 문제. 문제가 굉장히 긴데, 실생활에서 흔히 마주칠만한 좋은 문제였다. https://www.acmicpc.net/problem/13302 13302번: 리조트 수영이는 여름방학을 맞이하여 많은 놀이 시설이 있는 KOI 리조트에 놀러가려고 한다. 리조트의 하루 이용권의 가격은 만원이다. 하지만 리조트의 규모는 상상을 초월하여 모든 시설을 충분히 www.acmicpc.net 의식의 흐름 및 해설 스키를 못타는 날이 중간에 껴 있더라도 이용권을 사용할 수 있어 문제 난이도가 낮아진 느낌. 만약 이런 조건이 없었다면 case_work가 좀 더 빡세졌을 것 같다. N이 100이기 때문에 시간복잡도가 상당히 널널하다. 현재 날짜에 스키를 탈 수 있다면 1일권, 3일권..

작년에는 사정 상 GoodBye, BOJ 2020! 을 참여하지 못했고, 나중에 연습삼아 풀어본 결과 1솔밖에 못하는 결과를 얻었다. 그래서 이번 GoodBye, BOJ 2021!에선 몇솔을 하든 상관없이, G3~2 까지의 문제들은 전부 해결해보는 것을 목표로 응시하였다. 프로징 전에 A~D 4솔, 프로징 후에 E를 시도했으나, 구현미스가 나서 5솔하지 못한 채 4솔로 마무리하였다. 결론적으론, 총 4솔로 마무리했다. 패널티가 좀 있기도 하고, E번을 해결하지 못했기 때문에 최종등수는 90등대이지 않을까 싶다. +) 22.01.01. 추가 확실히 E가 어려웠던 것 같다. 84등의 좋은 성적을 거두었다 ㅎㅎ 확실히 1년 전에 비해 많이 성장했음을 느끼는 계기가 된 대회였다 ㅎㅎ 간단하게 문제 별 느낀 점 ..

인터랙티브 문제는 어떻게 푸는걸까? 물론 백준 대부분에선 인터랙티브 문제를 어떻게 풀어야 하는지 하단에 힌트를 통해 친절하게 알려주는 편이긴 하다. 이번엔 https://www.acmicpc.net/problem/18649 문제와 https://www.acmicpc.net/problem/23306 문제 풀이를 보면서 인터랙티브를 어떻게 푸는지 살펴보려 한다. 참고로 인터랙티브 태그에 '함수구현' 문제도 좀 있는 편인데, 이건 프로그래머스 스타일을 한번이라도 봤으면 쉽게 접근할 수 있고, 인터랙티브와 함수구현은 엄연히 다르다고 생각해 '함수구현'문제는 여기서 풀지 않을 것이다. 23306. binary는 호남선 https://www.acmicpc.net/problem/23306 23306번: binary는..

세종과학예술영재학교(세과영)에서 4시간 반동안 열리는 SASA 프로그래밍 오픈컨에 참여해보았다. 시간도 마침 괜찮았고, 오랜만에 대회 참여하면서 실력 점검 및 유지해보면 좋을 듯했기 때문이다. 그리고 2솔 이상하면 프로필 뱃지를 준다길래 참여해보았다 ㅎㅎ 대회 내에 풀 수 있는 문제들은 잘 푼 것 같다. 큰 실수로 인하여 풀 수 있는 문제를 놓치는 경우는 존재하지 않은 듯하고, C2번과 H번이 풀릴 듯 말 듯했다. (다행히 다음날에 업솔빙 성공) 문제들이 상당히 재밌었다. 오랜만에 대회를 참여해서 그런진 모르겠는데 정말 재밌게 푼 듯하다. 다만, B번 지문이 이해하기 꽤 어렵게 되어있었고, 2021년 12월 13일 기준, 에디토리얼이 없다는 점은 아쉬웠다. 에디토리얼도 없으니 포스팅에 코드 및 풀이를 간..

대회 오픈컨 당일에 사정상 참여할 수 없어 뒤늦게 시간재고 풀어보는 시간을 가졌다. 오픈컨은 7시간동안 15문제였던 것으로 기억하는데, 7시간 내내 ps에 시간투자하긴 어려울 듯하여, 14~17시동안 Master 8문제를 해결해보는 시간을 가졌다. 진행 방식: 그룹 연습 / 티어: 성공한 문제에만 표시 / 알고리즘 분류: 보지 않음. / 그 전에 해결한 문제: 없음. 오픈컨 참가한 사람들에게는 solvedac 캐릭터가 판교역 옆에 서있는 배경을 주던데, 나는 오픈컨 참여는 하지 못했기 때문에 받지 못했다. 간단하게 후기를 작성해보겠다. 23738. A - Ресторан 대문자로 이루어진 문자열을 입력받으면 소문자로 바꿔주되, 특정 문자는 별도로 replace해주어야 하는 문제였다. 크게 어렵지 않은데,..

재밌는 문제가 뭐있을까 둘러보다가 발견한 문제. 마침 우리 학교에서 푼 사람이 아무도 없기도 해서 랭작용으로도 좋을 듯 해서 풀어보았다. 문제는 아래와 같다. https://www.acmicpc.net/problem/11877 11877번: 홍수 용량이 정확히 X인 히스토그램을 만들 수 없다면 첫째 줄에 -1을 출력해라. 그렇지 않다면 용량이 X가 되는 히스토그램의 열 h1, h2, …, hN를 출력해라. 그러한 방법이 여러 개가 있다면 아무 것이 www.acmicpc.net 문제 해석이 조금 껄끄러울 수 있는데, 쉽게 말해서 1~N까지의 높이로 이루어진 기둥들만으로 히스토그램을 만들되, 양옆 높이가 자신 높이보다 낮을 경우 물이 새므로 불가능하며, 맨 끝쪽에는 물이 없어야 한다는 소리다. 의식의 흐름 ..

이번에도 UCPC 문제 포스팅이다. 트라이 구현코드를 바꾼 후, 처음으로 해결해본 응용 문제인데, 구현코드가 익숙하지 않아서였는지 꽤나 고생을 했던 문제이다. 문제는 아래와 같다. https://www.acmicpc.net/problem/17365 17365번: 별다줄 먼 옛날에 문래빗어라는 언어가 있었다. 문래빗어에는 여러 개의 단어가 있었고, 사람들은 단어들을 나열해서 문장을 만들었다. 예를 들어 "ryan", "is", "lion" 세 단어로 "lion is ryan is lion"이라는 문 www.acmicpc.net 의식의 흐름 및 해설 예제입력1의 결과가 왜 109인지 직접 생각해보면 문제 이해에 도움이 된다. 해석하려는 단어가 aaaa 일 때, a는 예제입력1의 세 단어 모두 가능하므로 3*..

예전에 UCPC 연습용으로 풀다가 해결하지 못한 문제이다. 기댓값 표현이 겁을 한사발 먹게 해주기도 했고, 그 때 당시 dp를 어려워했기 때문이 아닐까 생각된다. 문제는 아래와 같다. https://www.acmicpc.net/problem/17367 17367번: 공교육 도박 공교육의 수호자 수찬이는 공교육의 정수라고 할 수 있는 한국정보올림피아드의 문제를 가지고 게임을 하려고 한다. 수찬이는 2010년도 한국정보올림피아드 시·도 지역본선 중등부 1번 문제를 www.acmicpc.net 의식의 흐름 및 해설 먼저, 주사위값마다 행동에 영향을 끼치는 것은 확실하다. 마침, 주사위도 최근 3개의 결과만 영향을 미치기 때문에 dp[100000+1][6+1][6+1][6+1]의 재귀 탑다운dp로 접근해볼 수 ..