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, ..