노는 게 제일 좋아

이 문제는 쉬웠지만 시간초과가 나는 이유를 간과했다. 분명 순서가 쓸모 없음에도.. 나는 순서를 고려하여 세지 않아도 되는 경우의 수까지 고려해서 시간 초과가 난 것이다. 그냥 무지성 백트래킹을 박아버렸다. https://www.acmicpc.net/problem/16922 #맞은 풀이 #include using namespace std; set counts; vector vec = {1,5,10,50}; // 최대 카운트, 현재 카운트, 현재 문자, 결과합 void func(int maxi, int cnt, int idx, int res){ if(cnt >= maxi){ counts.insert(res); return; } //문자의 순서는 상관없으므로 각 문자의 개수만 고려한다. //1번문자 a개 2..

전형적인 DP 문제다. 다만 조건을 곁들인? DP인 것을 쉽게 파악하였으나 조건을 만족시키려면 어떻게 해야하는가를 좀 많이 고민했다. 결국 하나씩 3개 돌리는 것이 답이었다. https://www.acmicpc.net/problem/17404 #맞는 풀이 #include #define R 0 #define G 1 #define B 2 using namespace std; const int MAX = 1002; int cost[MAX][3]; int house[MAX][3]; int main(){ ios::sync_with_stdio(0); cin.tie(0); int num; cin >> num; for(int i = 1; i cost[i][j]; } int ans = 123456789;// 충분히 큰 ..

브루트포스지만 식이 잘 생각이 안난다. 솔직히 어떻게 풀어야겠다라고 생각을 해야 모든 케이스를 뒤지는건데 그렇지 않으면 풀지 못한다. 이 리모컨은.. 1. 그냥 돌리는게 더 빠르잖아? 2. 번호를 누르는게 더 빠르잖아? 3. 번호를 우선 누르고 그 뒤에 돌리는게 빠르잖아? 위 3가지를 고려해야한다. 100 - 101은 그냥 버튼 하나만 누르면 되는 거고 그런 식이다. https://www.acmicpc.net/problem/1107 #맞은 풀이 #include using namespace std; bool button[10]; //false //해당 채널로 이동하기 위한 숫자입력 횟수 int possible(int n){ //0번 채널로 이동하는 경우 if(n == 0){ //고장나면 숫자로 이동 불가능..

실수하기 쉬운 문제고 나도 실수했다. 그리고 처음부터 생각하기는 쉽지 않다. 비트마스킹으로 풀만한 문제였다. 2^10 = 1024 https://www.acmicpc.net/problem/2800ㄴ 2800번: 괄호 제거 첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개 www.acmicpc.net #맞은 풀이 #include using namespace std; //괄호를 "한 쌍"씩 뺀 경우, 집어넣은 경우 => 모든 경우해야할듯 int maxNum = 0; stack pos; vector pairPos; set answer;..

이 문제는 스택에 관한 예외처리를 하는데 도움이 된다. 순서를 잘 생각해야 하는 문제다. 대충 답을 끼워맞춘 느낌이고 코드가 정제되지 않았지만 이런 식으로 푸는 듯 하다. https://www.acmicpc.net/problem/17413 #맞은 풀이 #include using namespace std; stack stk; string s; int main(){ //띄어쓰기 포함 모든 문자열을 받아야함 getline(cin, s); bool isTagging = false; //Tagging 중일 때, 아닐 때 //공백을 만났을 때, 아닐 때 for(char c : s){ if(c == ''){ cout

저자: 조지 하이네만 #책소개 더 효율적이고 창의적인 코드 작성을 위한 알고리즘 사용법 어려운 개념이나 수식 없이 그림과 예제로 학습하기 좀 더 똑똑한 코드로 프로그램 성능을 향상하고 싶다면 이 책을 펼쳐보자. 이 책은 소프트웨어 개발에서 가장 많이 활용되는 핵심 알고리즘을 각각 언제, 어떻게 사용하면 좋은지 단계별로 상세히 알려준다. 알고리즘 진행 과정을 시각화한 그림과 함께 예제 코드를 한 줄씩 알기 쉽게 설명하며, 성능을 직접 측정해볼 수 있도록 실행 가능한 코드를 제공한다. 장마다 수록한 연습 문제는 문제 해결 능력을 향상해 코딩 인터뷰를 준비하는 데도 도움이 된다. 전문 개발자뿐 아니라 자신의 연구 분야에 알고리즘을 적용하려는 사람 모두에게 유용하다. 컴퓨터 과학에 관한 배경지식이 없어도 프로그..

이것도 재밌고 문제로 나오지 않을까? 싶다. https://www.acmicpc.net/problem/2146 #맞은 풀이 #include using namespace std; #define X first #define Y second int dx[4] = {1,-1,0,0}; int dy[4] = {0,0,1,-1}; int N; int conti[100][100]; int area[100][100]; int dist[100][100]; int flag = 1; int minDist = INT_MAX; void DFS(int x, int y){ area[x][y] = flag; for(int dir = 0; dir= N || ny = N)continue; if(area[nx][ny]..

어렵진 않지만 실수할 경우가 많은 문제가 아닌가 싶다. https://www.acmicpc.net/submit/14225/44550103 #맞은 풀이 #include using namespace std; int N; vector vec; unordered_map dict; //그냥 숫자체크 void func(int cnt, int result){ if(cnt == N){ //cout N; for(int i = 0; i> x; vec.push_back(x); } func(0,0); long long num = 1; while(true){ if(dict[num] == 0){ cout

쉬운 문제다. 백트래킹의 전형적인 형태를 보여준다. https://www.acmicpc.net/problem/6603 #맞은 풀이 #include using namespace std; vector vec; //6개 뽑으면 종료 => 조건 사전순, 조합, 현재까지 뽑은 결과 void func(int cnt, vector result, int cur){ if(cnt == 6){ for(auto c : result){ cout

전형적인 BruteForce다. 다만. 10자리라는 숫자는 큰 숫자이기에 나같은 범위를 착각하는 실수를 하지 않기를 바란다. https://www.acmicpc.net/problem/2529 #맞은 풀이 #include using namespace std; int k; vector vec; long long maxN = -9999999999; //범위 조심 string MM; long long minN = 9999999999; //범위 조심 string mm; bool check[10]; bool IsValid(int a, int b, int seq){ if(vec[seq] == '>'){ return a > b; }else{ return a < b; } } void func(int cnt, string..