너구리의 코딩 블로그

문제 풀이 풀이에 대한 여러 방법을 고민해보았던 문제입니다. 처음에는 2차원 배열을 만들어 DP 방식으로 풀려고 했었는데 로직이 생각보다 간단하고 비교 연산이 많지 않아서 재귀를 이용해 풀이하였습니다. 일단 가장 많은 금액을 받기 위해 주어진 일수 동안 할 수 있는 모든 경우를 탐색하며 최적의 값을 찾았습니다. 재귀에서 idx변수는 0번 회의부터 마지막 회의까지 탐색하기 위한 인덱스입니다. 만약 idx번째 회의를 진행할 수 있다면 --> 현재 회의에 걸리는 일수가 N보다 작거나 같다면 ( = idx + T[idx]

문제 풀이 총 아홉명의 난쟁이들의 키가 입력으로 주어집니다. 일곱 명의 난쟁이를 선택하기 위해 아홉명 중에서 두 명이 빠진 경우 중에서 일곱 난쟁이의 키가 100이 되는 경우를 찾았습니다. 먼저 난쟁이들의 키를 입력받았고 sum 변수에 난쟁이들의 키의 합을 저장했습니다. 가능한 경우에 대해서 오름차순으로 출력해야 하므로 Arrays.sort( ) 를 이용해 정렬하고 시작하였습니다. for문을 이용하여 두 명의 난쟁이를 제외시킵니다. 가장 바깥쪽에 있는 i와 j 를 이용해 두 명의 난쟁이를 찾고 만약 이 두 난쟁이의 키 값을 뺀 키의 합이 100이 될 경우 ( = sum - arr[ i ] - arr [ j ] == 100 ) 난쟁이의 키를 출력하도록 해주었습니다. 해당하는 난쟁이 조합을 찾으면 boole..

문제 풀이 브루트포스 방식으로 문제를 풀었습니다. year와 연월일에 해당하는 e, s, m 을 모두 1씩 증가시켜주면서 입력으로 주어진 연월일과 같은 출력이 나올 때까지 계속 탐색합니다. 처음에는 % (mod) 연산을 이용해서 풀이를 하려 했지만 예를 들어 e가 16에 해당할 경우 e가 0이 아닌 1로 바뀌어야 하기 때문에 그냥 1씩 증가시켜주었습니다. 코드 출처 https://www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타내는 수를 E, 태양을 나타내는 수를 S, 달을 나타내는 수를 M이..

문제 풀이 #1. Input( ) 부분 치즈가 있는 부분을 map 배열에 1로 표시해주었고 치즈 수를 세기 위해 cheese 변수를 1씩 ++해주었습니다. #2. Main 부분 Main에서는 while 문에서 치즈의 갯수가 0이 아닐 때까지 Melting( )과 Clear( ) 함수를 계속 반복합니다. 치즈가 모두 녹아서 사라지는 데 걸린 시간을 알기 위해 Time 변수를 while문을 실행할 때마다 1씩 늘려주었고, 모두 녹기 전에 ( Cheeze가 0이 되기 전 ) 남아 있던 치즈의 갯수를 알기 위해 Ctmp 변수에 이전 치즈 값을 저장하였습니다. #3. Melting( ) 부분 이 문제에서 판의 테두리 'X' 부분에는 치즈가 위치하지 않습니다. 이를 이용하여 '치즈가 없는 바깥 부분, 또는 치즈가 ..

풀이 문제에서 자연수는 최대 4자리라고 하여 int[4] 배열을 하나 만들어주었습니다. 숫자를 문자열 String으로 입력받아 그 길이만큼 반복하면서 ( for의 N.length( ) ) CharAt( ) - '0' 연산을 이용해 각 자리수의 값을 sum에 더해주었습니다. 문자열을 CharAt()으로 뽑아내게 되면 하나의 문자 상태가 됩니다. '0' 문자 0은 우리가 사용하는 10진수 int 0과 같지 않으므로 문자를 숫자로 변경해주기 위해 마이너스 ' 0 ' 연산을 해주는 것입니다. 코드 출처 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5QPRjqA10DFAUq&categoryId=AV5QPRjqA10DF..

문제 풀이 문제에서 주어진 위치로부터 상점들의 위치들까지에 대한 최단 거리의 합을 구하는 문제입니다. 상점까지의 거리는 시계 방향과 반시계 방향으로 나뉘기 때문에 저는 각각의 Case들에 대해 if else문과 switch문을 이용한 조건 반복문으로 풀이하였습니다. 코드가 상당히 길어지기 때문에 비효율적으로 풀이한 것 같습니다. 각각의 경우에 대하여 블록의 가로, 세로 길이 N과 M은 고정되어 있기 때문에 시계 방향으로 상점을 찾아갈 경우와 반시계 방향으로 찾아갈 경우를 Math.min ( ) 함수를 이용하여 최단거리를 answer 변수에 계속 더하여 최단 거리의 합을 찾았습니다. 코드 출처 https://www.acmicpc.net/problem/2564 2564번: 경비원 첫째 줄에 블록의 가로의 길..

문제 풀이 Union-Find를 이용하여 풀이해야 하는 문제입니다. 0일 때 union 연산을 수행하고 1일 때 같은 집합에 있는지를 비교하기 때문에 flag 변수를 만들어서 분류해주었습니다. 문제에서 여러 번 isSame( ) 연산을 수행하기 때문에 StringBuilder( ) 를 이용해서 한 번만 출력할 수 있도록 해주었습니다. 추가적으로, union( ) 연산에서 연산의 수행속도를 높여주기 위해 x y 중 큰 수를 부모로 바꾸어주도록 하였습니다. 코드 출처 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연..

문제 풀이 먼저 각각의 알파벳이 나온 빈도수를 체크하기 위해 alpha[ ] 배열을 만들어주었습니다. 입력받은 str을 한 글자씩 잘라 보면서 alpha 배열에 카운트를 1씩 증가시켜주어 몇 번 등장했는지 알 수 있도록 해주었습니다. 카운팅을 완료한 이후 max와 max_idx를 만들어 max는 가장 높은 빈도수, idx는 max값일 때의 문자를 기록하기 위해 두 변수를 사용했습니다. 추가적으로 max값이 똑같을 경우, ? 를 출력해주어야 하기 때문에 이를 구분하기 위한 flag 변수를 만들었습니다. 새로운 max값이 등장할 때 if문 안에서 flag를 false로 초기화해주었고, 만약 똑같은 max 값이 발생한다면 flag를 true로 바꿔 그 경우에는 결과값? 를 출력해주었습니다. 코드 출처 http..

문제 풀이 최소공배수, 최대공약수를 구하는 연습을 백준 2609번 문제를 통해 연습해보도록 하겠습니다. 문제 풀이는 유클리드 호제법을 이용하였습니다. https://namu.wiki/w/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C%20%ED%98%B8%EC%A0%9C%EB%B2%95 유클리드 호제법 - 나무위키 이 저작물은 CC BY-NC-SA 2.0 KR에 따라 이용할 수 있습니다. (단, 라이선스가 명시된 일부 문서 및 삽화 제외) 기여하신 문서의 저작권은 각 기여자에게 있으며, 각 기여자는 기여하신 부분의 저작권을 갖습니다. 나무위키는 백과사전이 아니며 검증되지 않았거나, 편향적이거나, 잘못된 서술이 있을 수 있습니다. 나무위키는 위키위키입니다. 여러분이 직접 문서를 고칠 수 ..

문제 풀이 BFS를 활용해야 하는 문제입니다. 주어진 맵 정보에 대하여 매 시간별 물이 차오르는 정보를 업데이트 해주어야 하고, 고슴도치는 한 칸씩 이동할 수 있습니다. 따라서 저는 먼저 fire() 함수를 통해 물이 차오르는 범위를 업데이트를 해준 뒤, bfs 함수로 고슴도치가 한 칸씩 이동할 수 있도록 해주었습니다. ※ 주의할 점 하나는 물이 차오른 뒤에 고슴도치를 이동시켜야 정상적으로 이동할 수 있기 때문에 bfs 함수 실행 전 fire 함수를 먼저 실행해주었습니다. ※ 주의할 점 두 번째로는 고슴도치가 비버의 굴로 이동할 수 없는 경우도 발생하기 때문에 이동하지 못하는 경우와 이동할 수 있는 경우를 위해 flag 변수를 활용하였습니다. while문의 조건으로 1. 아직 도달하지 못했을 때 ( ! ..