Ikjo's Technology blog

문제 설명 1052번: 물병 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번 www.acmicpc.net 접근 방법 해당 문제에서는 N개의 물병을 재분배하면서 최종적으로 남은 '비어있지 않은' 물병이 K개 이하일 경우 (나머지는 모두 빈 물병) 상점에서 최소한으로 산 물병의 개수를 요구하고 있습니다. 그렇다면 N개의 물병을 재분배하는 과정을 먼저 살펴보겠습니다. 우선 N = 1일 때는 K가 1이든 1000이든 (K의 값은 최소 1, 최대 1000) 항상 K 이하이므로, 상점에서 추가로 상점에서 물병을 사올 필요가 없습니다. N = 2일 때는 최초 물병의 용량은..

문제 설명 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 접근 방법 해당 문제는 규칙성을 세워서 해결할 수 있었습니다. 우선 주어지는 x 좌표와 y 좌표 사이의 거리(y - x) 일부(1 ~ 16)에 대해 공간 이동 장치 작동 횟수(이하 '이동 횟수')의 최솟값을 일일이 구해 나타내보면 다음과 같습니다. 이때 이동 경로를 통해 하나 유추해볼 수 있는 것은 만일 거리(distance)의 값이 제곱수(1, 4, 9, ...)에 해당된다면, 이동 횟수는 '해당 제곱수의..

문제 설명 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 접근 방법 결론적으로 해당 문제는 너비 우선 탐색을 이용하여 해결할 수 있었으나, 처음에는 백트래킹으로 접근 했었습니다. 백트래킹으로 접근, 결과는 시간 초과 입력될 수 있는 명령어에 대한 모든 경우의 수를 고려하고자 했고, 가장 짧은 명령어를 찾기 위해 명령어 조합의 수를 첫째 자리부터 대략 100번째 자리까지(임의로 둔 것) 일일이 백트래킹을 해주도록 했습니다. 탐색 중 타겟 숫자와 동일해지는 순간 해당 명령어를 출력 시키도록 했지만,..

문제 설명 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 접근 방법 문제의 입력값으로 최초 n개의 각각의 노드별로 부모 노드가 주어지는데, 이를 해쉬 맵 자료구조에 저장합니다. 이때 루트 노드는 부모 노드가 없으므로 루트 노드만 따로 별도의 변수(rootNodeIndex)에 저장해주도록 합니다. BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); St..

문제 설명 25332번: 수들의 합 8 $A = \{1, 2, 3\}$, $B = \{1, 3, 2\}$로, 조건을 만족하는 $i, j$ 쌍은 $(1, 1), (2, 3), (1, 3)$의 세 가지이다. $A_1$ = $B_1 = 1$ $A_2 + A_3 = B_2 + B_3 = 5$ $A_1 + A_2 + A_3 = B_1 + B_2 + B_3 = 6$ www.acmicpc.net 접근 방법 해당 문제는 원티드 주관 코딩테스트 대회 2022년 2회차의 마지막 문제로서 단순하게 해결할 수 있어 보였지만, 시간 제한 등의 이슈로 다소 깐깐했었던 문제였습니다. 특히, 이 문제의 경우 백준 2015번 문제 '수들의 합 4'과 매우 밀접한 관련이 있는 문제이기에 해당 문제를 풀기 앞서 '수들의 합 4' 문제를 ..