버러범의 개발이야기

BOJ 문제 링크: https://www.acmicpc.net/problem/14698

슬라임이 각 에너지를 갖고 있고, 두 슬라임이 합쳐져서 생긴 슬라임이 갖는 에너지는 두 슬라임의 에너지 곱과 같다.

두 슬라임을 합치기 위해서는 각 슬라임이 갖고 있는 에너지의 곱만큼의 전기가 필요하다.

여러개의 슬라임이 주어졌을때 이 슬라임들을 하나의 슬라임으로 만들기 위한 전기의 최솟값을 구하는 문제이다.

직관적으로 에너지가 최소인 두 슬라임을 합쳐가기를 반복하는 그리디 알고리즘을 사용하면 답을 구할 수 있을거 같다.

priority_queue를 사용하면 이를 쉽게 구현할 수 있다.

참고로 원래 그리디 알고리즘을 사용할때는 정당성증명까지 신경쓰면서 문제를 풀어야 되지만,

이전에 알고스팟 문제로 풀었던 문자열 합치기랑 정당성증명 부분이 똑같은거 같아서 그냥 그리디 알고리즘을 사용했다.

MOD를 사용하는 부분에서 마지막에만 나머지를 취하는게 아니라 계산 도중 ret값에 나머지를 취하는걸 볼 수 있는데,

이렇게 하는 이유는 ret값이 longlong범위를 벗어나 오버플로우가 나는 것을 방지하기 위해서다.

이렇게 할수 있는 이유는 (A * B * C * D * . . . ) % MOD == (A * MOD) * (B * MOD) * (C * MOD) * (D * MOD) * . . . 의 원리와 같다.

사실 문제를 풀면서 계속 시간초과가 나와서 엄청 헤맸다. 처음에는 알고리즘 자체에 효율성이 떨어져서 시간초과가 나는줄 알고 한참 생각했다.

그러다 도저히 모르겠어서 일단 입출력을 cin, cout보다 빠른 scanf, printf를 바꿔서 제출했더니 정답이 나..왔더뻐..ㄱ

앞으론 scanf, printf를 더 애용해야겠다.

코드 원본: https://github.com/sbl133/BOJ/blob/main/%2314698.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

BOJ 문제 링크: https://www.acmicpc.net/problem/17828

각 알파벳 A, B, C, . . ., Z 순서대로 1, 2, 3, . . ., 26만큼의 화폐가치가 있다.

길이가 N인 알파벳을 나열한 문자열을 만들어서 각 문자의 화폐가치의 합이 X인 문자열 화폐를 만들려한다.

주어진 조건을 충족하면서 사전순으로 가장 빠른 문자열을 출력하자.

문자열이 사전순으로 가장 앞서려면 A를 앞쪽에 최대한 많이 나열하면 된다는것을 직관적으로 알수 있다.

그러기 위해서는 Z를 뒤로 최대한 많이 배치해서 주어진 화폐가치를 최대한 채우고, 남은 자리는 A로 채운다.

이때, A와 Z사이에 남은 화폐가치를 채우기 위한 가치가 2~25사이인 문자가 하나 올 수 있다.

코드 원본: https://github.com/sbl133/BOJ/blob/main/%2317828.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

BOJ 문제 링크: https://www.acmicpc.net/problem/15686

집과 치킨가게의 좌표가 N*N배열 형태로 주어진다.

m개의 치킨집을 남기고 구할 수 있는 각 집에서 가장 가까운 치킨 집과의 거리 합의 최솟값을 구하는 문제이다. 

집들과 치킨집들의 좌표를 각각의 벡터로 관리해준다.

좌표로 주어진 치킨집들중에 m개의 치킨집을 남겨야되는 작업은 재귀를 통해서 치킨집을 전체 순회하면서 구할 수 있다.

현재 치킨집을 남기는 경우와 폐업시키는 경우를 각각 재귀호출해서 더 작은 값을 반환 하는 쪽의 도시 치킨 거리를 반환한다.

코드 원본: https://github.com/sbl133/BOJ/blob/main/%2315686.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

BOJ 문제 링크: https://www.acmicpc.net/problem/12865

배낭에 담을 수 있는 무게가 제한 되있고, 각 물건들의 가치와 무게가 주어진다.

이때 배낭에 담을 수 있는 물건들의 가치의 최댓값을 구하는 문제이다.

주어진 물건들을 차례대로 순회하면서 담을지 안담을지를 결정한다. 담았을 경우 현재 배낭에 무게에 담고자 하는 물건의 무게를 추가하여 다음 물건을 결정하는 재귀를 호출하고, 안담았을 경우 현재배낭에 무게 그대로 다음 물건을 결정하는 재귀를 호출한다. 이 두 재귀중 큰 값을 반환하는 경우의 값을 return하면 된다.

코드 원본: https://github.com/sbl133/BOJ/blob/main/%2312865.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

BOJ 문제 링크: https://www.acmicpc.net/problem/14503

로봇 청소기가 청소할 방에 벽과 청소가 안되있는곳을 각각1, 0으로 표현한 2차원 배열이 주워진다.

조건에 맞게 로봇청소기가 움직였을때 청소한 칸의 갯수를 출력하는 문제이다.

문제에 주어진 경우들을 switch문으로 나누어서 재귀호출하는 형식으로 문제를 해결할 수 있었다.

코드 원본: https://github.com/sbl133/BOJ/blob/main/%2314503.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

BOJ 문제 링크: https://www.acmicpc.net/problem/9251

두 수열이 주어졌을때, 모두의 부분 수열이 되는 수열 중 가장 긴 것(LCS)을 찾는 문제이다.

두 수열을 순회하면서 두 수열중 하나가 다음 문자로 넘어가거나, 두 수열을 가르키는 문자가 서로 같으면 LCS에 추가하고 둘다 다음 문자로 넘어가는 재귀 호출을 하면서 가장 큰 값을 리턴하는 경우를 찾는다.

코드 원본: https://github.com/sbl133/BOJ/blob/main/%239251.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

BOJ 문제 링크: https://www.acmicpc.net/problem/2812

N자리 숫자가 주어졌을때, K개의 숫자를 지워서 얻을 수 있는 가장 큰 수를 구하는 문제이다.

문제 유형은 그리디였지만 덱을 이용하면 문제를 쉽게 풀 수 있어서 자료구조의 중요성을 더 깨닫게 되었다.

먼저 주어진 숫자들을 순회하면서 현재 숫자가 덱에 있는 숫자보다 크면 덱에 있는 숫자들을 꺼내고 해당 숫자를 넣는다. 얼핏보면 스택구조를 이용해서도 문제를 풀 수 있을거 같지만 마지막에 삭제하고 남은 숫자들을 출력하는 과정에서 스택으로 치면 맨 밑에 있는 숫자부터 출력 해야하기 때문에 덱 구조가 더 문제에 적합하다.

코드 원본: https://github.com/sbl133/BOJ/blob/main/%232812.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!