Oriburger's Log

[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