본문 바로가기

Problem Solving/백준

 (80)
[백준/C++] 4779번 칸토어 집합 문제 해석 문제 풀이 보자마자 분할 정복인 것은 알았으나 분할정복을 제대로 이해하고 있지 않아서 선으로 문자열을 먼저 만들고 지워나가는 형식으로 구현하려고 했으나 어려워서 헤맸다. (개인적으로 분할정복이 제일 어렵다) 이 문제는 아래와 같은 패턴이다. N == 2는 N == 1을 2번 더하고 사이에 N==1 만큼의 공백이 있고 N==1은 N==0을 2번 더하고 사이에 공백이 N==0 만큼 존재한다. 따라서 이전 것을 그리고 이전 사이즈만큼 공백을 그리고 이전 것을 그려주는 형식으로 분할하면 되는 문제이다. 정복할 때는 N == 0인 초기상태일 때 ' - ' 를 그린다. 코드 #include using namespace std; int N ; void Div_Con(int n) { int str_sz = ..
[백준/C++] 19539번 사과나무 풀이 처음에는 결국 모든 숫자를 만들 수 있으니 전체 합이 3의 배수인지만 확인하면 되는거 아닌가? 했다. 1 1 1 3 3 이면 반례가 생기는 것을 알게 되었다.. 3의 배수는 만들 수 있는 숫자니 일단 모든 숫자는 3으로 나눈 나머지로 바꾼 후 1의 갯수와 2의 갯수를 비교하면 되지 않나? 했다. 10 1 1이 반례가 되었다. 뭔가 2가 실마리가 되는 것 같은데 20분이 지나서 힌트를 참조했다. 괜히 참조한 것 같다. 조금만 더 고민해볼 걸 결국 3의 배수이면서 2의 갯수가 물뿌리는 토탈 횟수보다 많으면 된다. reason 전체 수의 합이 3의 배수이면 물뿌리개를 동시에 사용해서 며칠이 걸리는지 체크 가능하다. (즉 배수가 아니면 물뿌리개를 동시에 사용해서 만들 수 없는 숫자이다.) 2만큼 성장하는 물뿌리..
[백준/C++/KOI] 2470번 두 용액 이분탐색 풀이 input은 최대 10억 최소 -10억의 정수값으로 10만개 이하가 들어온다. int로 처리할 수 있으며 투포인터로 처리하기 전에 이분탐색으로 풀었는데 투포인터 풀이가 조금 더 쉬운 것 같다. 이분탐색은 푸는데 하루종일 걸렸는데 투포인터는 30분 내로 풀어졌다. (같은 문제라서 그럴지도 모른다.) 투포인터 풀이 링크: https://readble-ko.tistory.com/147 #include using namespace std ; class Best { public: int first ; int second ; int val ; Best(){ first = 0, second = 0, val = 2e31 - 2; } }; int N ; Best best = Best() ; int main() { ios..
[백준/C++/KOI] 2467번 용액 투포인터 풀이 input은 최대 10억 최소 -10억의 정수값으로 10만개 이하가 들어온다. int로 처리할 수 있으며 투포인터로 처리하기 전에 이분탐색으로 풀었는데 투 포인터가 더 쉬운 것 같다. 생각해보면 정렬한 후에 각 용액에 대한 페어를 찾아내면서 최소값을 찾는다는 그리디함이 보장되는 문제였다. 이분탐색 풀이 링크: https://readble-ko.tistory.com/148 #include using namespace std ; int N ; class Best //합이 가장 적은 경우를 best 클래스에 저장했다. { public: int val = 2e9 ; //최대 + 최대 case를 생각해 20억으로 맞춰주었다. int first = 0 ; int second = 0 ; }; int main() { ..
[백준/C++] 19238번 스타트 택시 풀이 문제만 읽어보면 쉬운 문제 같은데 생각보다 함정이 많은 문제였다. [함정1]. BFS로 위쪽, 왼쪽, 오른쪽, 아래쪽 순으로 돌리면 가장 행이 적은 순, 가장 열이 적은 순이 보장되지 않는다. (예시: 왼왼왼, 오오위의 경우 후자가 우선순위이지만 왼왼왼을 먼저 찾게 된다) [함정2]. 어떤 사람의 도착점이 다른 사람의 출발점이 될 수 있다. 혹은 택시의 시작점이 사람이 있는 지점이 될 수 있다. 이 외에도 함정이 좀 있었던 것 같은데 나는 이 2가지를 처리하고 보니 AC를 받게되었다. 코드를 짤 때 로직을 아래와 같이 짰다. BFS_1(현재위치) - 조건에 따라 택시에서 가장 가까운 곳을 찾아서 좌표를 리턴해준다. BFS_2(현재위치, 승객위치) - 현재위치에서 승객 위치까지의 거리를 BFS로 찾아서 넘..
[백준/C++] 17138번 캐슬 디펜스 풀이 최대 N과 M이 15이고 궁수는 3명이니 브루트포스로 실행할 경우 최대 225C3이다. 이는 대략 180만번이고 각각에 궁수가 15턴을 실행할 경우를 계산하면 180만 * 15 * 3으로 8천만번이고 1억번 이내이므로 브루트포스로 풀어낼 수 있는 문제이다. 먼저 궁수 3명의 위치를 선정하기 위해 SetArcher 함수로 모두 구해주었다.이후 Simulate 함수를 통해 15턴동안 어떤 궁수가 어디 위치한 적을 쐈는지를 체크하고 죽인 적은 제거해주었다.이 때 매 턴이 지나가는 것을 15x15 게임맵을 아래로 한칸씩 내리고 위에 0으로만 이뤄진 배열을 추가해주었다. 매 턴마다 PlayOnTurn 함수를 실행시켰으며 이 함수에서 BFS로 가장 가까이 있으면서 가장 왼쪽에 있는 적을 우선적으로 찾아주었다. 만약..
[백준/C++] 1043번 거짓말 BFS 풀이 문제를 읽고 testcase를 쭉 훑어보니 결국 진실을 알고 있는 사람과 연결되지 않은 사람들로만 구성된 파티를 찾아내는 것으로 인식했다. 먼저 진실을 알고 있는 사람을 queue에 넣고 같은 파티를 edge로 판단했다. 이후 연결된 모든 사람들을 BFS로 미리 찾는 것을 생각했다. 이후 파티 명단을 보면서 아까 BFS를 통해 찾아낸 사람이 1명이라도 있다면 거짓말을 칠 수 없다고 코드를 짜고 실행시켰는데 한번에 통과를 받았다. 알고보니 이 문제는 유니온파인드(분리집합)문제인데 알고나서 문제를 보니 정말 그랬다. 다음에 시간나면 유니온파인드로도 풀어서 풀이를 올려야겠다. #include using namespace std; queue que ; vector party[51] ; int graph[51][..
[백준 / C++] 2295번 세 수의 합 풀이 처음 문제를 읽었을 때는 N의 개수가 최대 1000개니 sorting한 이후 3개씩 슬라이딩 윈도우로 브루트포스 방식을 취하면 풀리지 않을까 생각하였으나, 슬라이딩 한 것들을 다시 확인 하는 방법에서 막혔고 다시보니 중복되게 선택할 수 있었다. 이후 map을 이용해 for문 3개 중첩을 무지성으로 시도하다 생각해보니 N3logN 이라 시간 초과 문제가 생겼다. (1000개를 3제곱하면 최소 10억이라 10초다. 심지어 map은 메모리 초과문제도 생겨 set으로 변경하였다) 더 이상 줄일 방법을 찾지 못해 힌트를 보았다가 다들 천재인가 싶었다. 풀이 방법은 간단하다. x,y,z 를 따로 구하지 않고 y,z를 합으로 한 배열(sum)을 하나 생성한다 (N2) 기존 배열을 arr라고 가정했을 때 x + y +..

티스토리툴바