문제https://www.acmicpc.net/problem/14948시간 제한메모리 제한solved.ac 티어1초256MB골드 2풀이 벽부수고 넘어가기 문제와 저번 1939번 문제를 섞어둔듯한 문제이다. 1939번에서 사용한 그래프탐색+이분탐색과 벽부수기 풀이를 섞어서 시도했지만, 진짜 계속해서 틀렸고, 어디서 틀렸는지 감도 잡히지 않았다. 결국 다른 분의 풀이를 아주 조금 참조했다. visited 배열을 2차원이 아닌 3차원으로 처리하는 테크닉을 보고, 아 이런 테크닉이 있었지 하고 코드를 개선했다. 물론 개선했다고 읽기 좋은 코드라는건 아니다... 코드도 정리해야할거 같다.WA코드#include using namespace std;int n, m, low, high;vector> rokaf;int ..
문제https://www.acmicpc.net/problem/1939시간 제한메모리 제한solved.ac 티어1초128MB골드 3풀이 장염도 거의 다 나았으니 다시 할일을 시작해야겠다. 오랜만에 밀린 문제 정리하기이다. 이 문제는 정말 인상적인 문제이다. 최단경로 문제같으면서도, 최단경로 문제라기엔 조금 어색한 문제이기 때문이다. 이 문제가 인상적이라고 느낀 이유는 그래프 탐색과 이분탐색을 섞은 문제이기 때문이다. 어떤 그래프에 대해 답이 a라고 한다면, a보다 작은 a'로도 해당 그래프를 통과할 수 있고, 무엇보다 다리의 중량제한이 최대 10억으로 매우 크다. 탐색의 범위가 넓고, 특정 값 기준으로 가능/불가능이 나뉘어지기 때문에 이분탐색을 사용하기 좋다. 이분탐색을 통해 특정한 중량을 정하고, 해..
문제https://www.acmicpc.net/problem/1967시간 제한메모리 제한solved.ac 티어2초128MB골드 4풀이https://codejin.tistory.com/294 백준 1167번 C++ 풀이문제https://www.acmicpc.net/problem/1167시간 제한메모리 제한solved.ac 티어2초256MB골드 2풀이 이 문제는 정말 며칠동안 고심하고 해결한 문제이다. 이 문제는 뭔가 무엇도 참조하지 않고 내가 직접 풀어codejin.tistory.com이 문제를 풀던 도중 쏟아져내리는 MLE에 정신을 못차리고 트리의 지름 문제를 백준에 검색했다가 나온 문제이다. 1167번에 비해 n이 10배 적고, 입력도 매우 착한 문제라고 할 수 있다. 풀이는 위의 1167번을 참조하자..
문제https://www.acmicpc.net/problem/1167시간 제한메모리 제한solved.ac 티어2초256MB골드 2풀이 이 문제는 정말 며칠동안 고심하고 해결한 문제이다. 이 문제는 뭔가 무엇도 참조하지 않고 내가 직접 풀어보고 싶다는 욕망이 들었고, 이를 실제로 행한 문제이다. 처음에는 별 생각없이 정점의 개수도 체크하지 않고 플로이드 워셜을 돌린 후, 트리의 지름을 찾고자 했다. 하지만 정점의 개수가 10만개인데 당연히 불가능한 풀이였고, 바로 폐기한 방법이다. 두번째는 내가 풀이한 방법이다. 임의의 정점을 골랐을 때, 트리의 지름을 구성할 때 내가 선택한 정점이 트리의 지름에 낄 수도 있고 아닐수도 있다. 정확히 말하면, 트리의 지름은 내가 현재 위치한 정점을 사용할 수도 있고, ..
문제 시간 제한메모리 제한solved.ac 티어1초128MB실버 1풀이 어제 오늘 장염에 걸려 제대로 문제를 풀지 못했다가, 오늘 기운이 좀 생긴 김에 랜덤 실버 문제를 후딱 풀어냈다. 이 문제는 사실 예전에 풀려고 했다가 실패하고, 어디서 틀렸는지 감을 잡지 못해 그대로 잊은 문제였는데, 랜덤으로 뽑았다가 이 문제가 나왔다. 조합을 계산하는 방법은 여러가지가 있다. 해당 글에서 두가지 방법을 사용했었다. https://codejin.tistory.com/172 백준 1010번 C++ 풀이https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이..
문제https://www.acmicpc.net/problem/15663시간 제한메모리 제한solved.ac 티어1초512MB실버 2풀이 며칠만인지 모르겠지만 아무튼 오랜만에 밀린 문제 정리하기다. 이번 N과 M은 원소를 조합으로 뽑는 문제이다. 언제나 그렇듯 사전 기준 오름차순 출력이기 때문에 입력받은 N개의 원소를 정렬한 후, 백트래킹으로 M개의 숫자를 중복없이(같은 인덱스의 원소를 뽑지 않고) 뽑는다. 이때 N개의 원소에는 중복되는 원소가 존재할 수 있다. 이를 모두 고르게 되면 중복되는 수열이 등장하게 된다. 이를 방지하기 위해 map에 출력한 output과 해당 값이 출력되었는지 기록하여, 중복된 수열이 나오더라도 출력은 한번만 되도록 했다.코드#include #define ALL(X) X.be..
문제https://www.acmicpc.net/problem/1715시간 제한메모리 제한solved.ac 티어2초128MB골드 4풀이 15903번 문제와 거의 같은 문제이다. 당시 문제 풀이는 https://codejin.tistory.com/203 에서 확인할 수 있다. 백준 15903번 C++ 풀이https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄codejin.tistory.com 결국은 제일 작은값 끼리 더해나가면서 값이 증가하는 폭을 최대한 줄이면 최종적인 합도 최솟값이 된다. 그리디하..
문제https://www.acmicpc.net/problem/1759시간 제한메모리 제한solved.ac 티어2초128MB골드 5풀이 문제를 읽어보면 정말 익숙한 그 냄새가 난다. N과 M 문제의 냄새가 말이다. 따라서 이 문제는 백트래킹이다. 물론 문자의 개수가 많지 않고 시간제한이 2초나 되기 때문에 입력받은 문자를 자음과 모음으로 나누어 일일이 브루트포스를 해도 답은 맞을 것 같다. 처음 문제를 풀고나선 WA를 받았는데, 자음 조건을 놓쳐서 틀렸다. 이런 실수는 줄여나가야 하는데 말이다...코드#include #define ALL(X) X.begin(), X.end()#define endl '\n'using namespace std;int l, c;string pwd, vowels, consona..
