Oriburger's Log

[2021년 08월 15일 21시 08분 작성] [PS][백트래킹] BOJ 1079 : 마피아 [문제 링크 : 클릭] 1. 풀이 백트래킹을 이용한 문제입니다. 함수 정의를 다음과 같이 두고, Solve(cnt) = 남은 사람이 cnt명, 최대로 보내는 밤의 횟수 각 조건에 맞게 코드를 작성해주면 해결할 수 있습니다. 자세한 설명은 코드에 주석으로 남겨두었습니다. +) 유의할 점 가장 오래 마피아가 버티는 경우는 마피아가 이기는 경우입니다. 즉, 위 함수에서 남은 사람이 1인 경우가 바로 정답입니다. 이 문제는 시간 제한이 있기 때문에, cnt가 1인 경우를 찾는 즉시 남은 경우들을 넘겨야 합니다. 2. 소스코드 [Github 링크 : 클릭] #include using namespace std; int n..

[2021년 08월 14일 21시 28분 작성] [PS][구현] BOJ 17480 : 개구쟁이 준석이 [문제 링크 : 클릭] 1. 풀이 구현하기 상당히 까다로운 문제입니다. 순서는 다음과 같습니다. 1. 문자열의 길이가 최대 14이기 때문에, 모든 부분 문자열에 대해 알파벳 개수 일치 여부를 탐색합니다. (Brute-Force) 2. 우선 반을 나눕니다. (길이가 홀수라면, mid값을 조정하여 1회 더 나눕니다) 3. 나누고 나서, 오른쪽 / 왼쪽 둘 중 하나를 골라 뒤집은 다음, 반대쪽 부분을 선택하여 2로 계속 진행합니다. ㄴ> 만약, 반대쪽 부분의 길이가 1이라면, 해당 문자열을 체크합니다. mid 값에 유의해서 코드를 전개해주면 해결할 수 있습니다 :) 2. 소스코드 [Github 링크 : 클릭]..

[2021년 08월 13일 11시 07분 작성] [PS][DP] BOJ 17485 : 진우의 달 여행(Large) [문제 링크 : 클릭] 1. 풀이 [BOJ 17484] 문제에서 값의 범위가 더 커진 문제입니다. 위 문제에서 정의한 함수에 메모이제이션을 적용시켜주면 해결이 가능합니다. Solve(y, x, last) : 현재 좌표가 (y, x)이고, 마지막으로 움직인 방향이 last일 때, 우주선이 달까지 가는데에 필요한 연료의 최소값 2. 소스코드 [Github 링크 : 클릭] #include using namespace std; const int INF = 2147000000; const int dx[3] = {-1, 0, 1}; int n, m, ans=INF, board[1001][1001]; i..

[2021년 08월 13일 23시 02분 작성] [PS][완전탐색] BOJ 17484 : 진우의 달 여행(Small) [문제 링크 : 클릭] 1. 풀이 Solve 함수를 다음과 같이 정의합니다. Solve(y, x, last) : 현재 좌표가 (y, x)이고, 마지막으로 움직인 방향이 last일 때, 우주선이 달까지 가는데에 필요한 연료의 최소값 위 함수에 맞게 재귀로 완전탐색을 돌려주면 해결할 수 있습니다. 2. 소스코드 [Github 링크 : 클릭] #include using namespace std; const int INF = 2147000000; const int dx[3] = {-1, 0, 1}; int n, m, ans=INF, board[7][7]; int Solve(int y, int x..

[2021년 08월 13일 22시 47분 작성] [PS][자료구조] BOJ 17479 : 정식당 [문제 링크 : 클릭] 1. 풀이 문제에 주어진 조건을 그대로 코드로 옮기면 됩니다. 또한, 메뉴--가격을 표현하기위해 unordered_map과 같은 해시 컨테이너를 사용해야합니다. +) 처음에는 주어진 주문을 순차적으로 조건을 따져서 정답을 구해줬습니다. --> 결과는 오답 파티... 그냥 주문 전체가 조건에 맞는지 여부를 따지면 해결할 수 있습니다. 2. 소스코드 [Github 링크 : 클릭] #include using namespace std; typedef unordered_map umap; //key가 string, value가 int형인 map string ans="Okay"; int a, b, ..

[2021년 08월 13일 22시 40분 작성] [PS][재귀] BOJ 17478 : 재귀함수가 뭔가요? [문제 링크 : 클릭] 1. 풀이 출력 예시를 보고, 재귀함수를 적절하게 설계하는 문제였습니다. 가장 깊이 있는 부분의 기저사례에 유의하여 재귀를 설계해주면 됩니다. 2. 소스코드 [Github 링크 : 클릭] #include using namespace std; int n; const string tmp = "____"; string str[5] = {"\"재귀함수가 뭔가요?\"\n", "\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.\n", "마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.\n", "그의 답은 대부분 옳았다고..

[2021년 08월 09일 19시 33분 작성] [PS][DP] BOJ 9764 : 서로 다른 자연수의 합 [문제 링크 : 클릭] 1. 풀이 문제를 조금 다르게 풀었습니다. "주어진 자연수 k를 서로 다른 여러 자연수를 빼서 0을 만들때, 총 몇 가지의 방법이 나오는가?" DP(k, n) --> k를 0으로 만드는 방법의 수 (이전 분기에서 마지막으로 사용된 수는 n) 위 함수 정의를 기반으로 코드를 전개해주면 해결이 가능합니다. +) MOD 연산을 각 분기마다 추가해주어 문제의 조건에 맞추도록 합니다. 2. 소스코드 [Github 링크 : 클릭] #include using namespace std; const int INF = 100999; int n; int cache[2001][2001]; //k를..

[2021년 08월 08일 17시 18분 작성] [PS][BFS] BOJ 9177 : 단어 섞기 [문제 링크 : 클릭] 1. 풀이 분류는 DP 문제였지만, BFS를 통해 해결하였습니다. 상태 노드는 int형 정수쌍 {a, b}로 정의합니다. {a, b} : str[0]은 a번째 문자를 뽑을 차례이고, str[1]은 b번째를 뽑을 차례 --> 이를 기반으로 메모이제이션을 적용해도 됩니다. {0, 0}부터 시작해서 두 개의 문자열 중에 하나를 뽑아 BFS를 진행하며 답을 찾습니다. +) 분기마다 방문 여부와, 다음 상태 노드가 정답 문자열로 옳게 나아가는지 판단하고, a와 b가 각 문자열의 길이를 넘지 않도록 조건을 걸어주었습니다. 그러면 현재 노드의 a+b가 str[2]의 길이가 같다면, 정답을 찾은것이므..

[2021년 08월 08일 17시 04분 작성] [PS][DP] 14916 : 거스름돈 [문제 링크 : (클릭)] 1. 풀이 기초적인 DP 문제입니다. 점화식을 아래와 같이 세우고, 코드로 옮겨주면 해결할 수 있습니다. DP(k) = INF (k= 0) ret = GetAnswer(k-2) + 1; if(k-5 >= 5) ret = min(ret, GetAnswer(k-5) + 1); return ret; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n; memset(cache, -1, sizeof(cache)); int ans = GetAnswer(n); cout