오늘 학원에서 써먹은 개념을 그대로 쓸수 있었던 문제 nHr 중복조합을 구현하면 되는 문제이다. 0

비트DP였다. 방문한 적이 있는 숫자들을 비트에 박아넣으면 된다. www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net dp[i][j][k] 를 현재 문자열 길이가 i이고, 지금 제일 앞 숫자가 j이고, chk 비트필드가 k일때로 뒀다. 더보기 #include #define MOD 1000000000 using namespace std; typedef long long ll; ll dp[123][12][19) return 0; if(len == n){ if(bit == (1

맞왜틀이 심했던 문제 vis배열을 초기화하자!! *복창중* www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 이상하리만치 MLE가 박혀서 결국 VIS배열 박았다... :thinking: #include using namespace std; queue q; int input,ans; int d1,d2,d3,d4; int k,t; string s; int vis[12345] = {0}; void bfs(){ while(!q.empty()){ k = q..

www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 보통 PQ두개 써서 구현하겠지만 나는 Multiset을 써서 구현해봤다 삽입은 O(logN), 삭제는 amortized O(1)에 동작하므로 충분히 AC를 받기에 적합한 시간복잡도이다. multiset::end()는 마지막 값보다 한칸 더 뒤에 있는 위치를 가리키므로 erase를 통해 지우려면 (--s.end())로 써줘야 정상적으로 지울 수 있다. 더보기 #include using namespace std..

특이한 풀이가 있어 쉬운 난이도인 실버 2임에도 불구하고 블로그 글을 써보려 한다. 원래 정해는 이제 최대공약수를 이용하는 풀이법이다. 최대공약수로 i 와 j를 나눠주면, 이 두가지 수가 이제 마치 "기약분수" 처럼 보이게 되고, 이를 통해 중복을 제거해줄수 있다. 하지만 여기서 기약분수라는 저 느낌을 잘 활용하면 소스코드의 길이를 대폭 줄일 수 있다. www.acmicpc.net/problem/10166 10166번: 관중석 KOI 공연장의 관중석에는 가운데에 있는 무대를 중심으로 반지름이 자연수인 동심원(중심이 같은 여러 원들) 위에 다음과 같이 좌석들이 배치되어 있다. 반지름이 1인 원 위에는 좌석이 1개, 반지 www.acmicpc.net 고등학교 2학년 교육과정에 라디안 각을 배우게 되는데, 이..

간선을 생으로 구현하면 MLE가 나오는 문제 간선의 갯수를 줄이기 위해서는 더미노드를 만들어서 하이퍼 튜브가 문어발 같은 느낌으로 펼쳐지게 설계해주면 된다. 그러면 모든 노드를 최소한의 간선만 가지고( 정점을 하나 더 써서 ) 이어줄 수 있고, 테스트케이스의 정답을 더미노드를 사용해서 문제를 해결하면 1 K 3 K 6 K 9 가 되는데, 정답, 즉 4를 N이라 하면 더미노드 K의 갯수는 N-1개 이다. 따라서 실제 정답은 우리가 bfs를 통해 구해준 가중치를 K로 두었을때 (K+1)/2를 출력해주면 답이 된다. 메모리 아끼는 팁으로는 가중치를 vis배열이랑 같이 묶어서 한번에 저장해줄 수 있다는 정도? 위의 더미노드를 만든다는 생각에만 도달하면 쉽게 AC를 받을 수 있다. 더보기 #include usin..