인생발전기원

#include #include #include using namespace std;long long solution(int r1, int r2) { long long answer = 0; for(int i=1; i 원의 방정식을 응용한 문제다.먼저 원의 방정식은 다음과 같다. 이를 응용하여 내부 원의 반지름 r1과 외부 원의 반지름 r2를 참고하면 다음과 같은 식이 성립한다. 위 식을 토대로 계산하면 또 다음과 같음을 알 수 있다. 따라서 x축을 고정시켜놓고, 위 공식을 통해 최소 Y값, 최대 Y값을 구해주면 된다.그리고 가능한 정수 값을 찾는 것이기에 최소의 경우 올림처리를, 최대의 경우 내림처리를 해서 맞춰주어야한다.추가로 주의할 점은 x 이 경우에 이후 계산식이 무조건 음수로 s..

#include #include using namespace std;int answer = 0;int arr[13];bool check(int n){ for(int i=0; i 퀸의 경우 가로세로 또는 대각선으로 이동이 가능하다.따라서 위 3가지 방향에 대해 고려를 해야한다. 우선 행을 고정시키고, 여기서 열만 바꿔서 퀸을 배치시킬 것이다.해당 값을 토대로 행을 옮겨 놓을 예정인 값의 유효여부를 판단하고, 가능하면 이어서 dfs 탐색을 이어나간다. 행을 고정시켰기에, 행을 탐색할 필요는 없다.따라서 남은건 같은 열인지, 또는 대각선인지 체크하는 것이다.반복문을 통해 놓을 예정인 위치가 이미 값이 존재하는 지 여부를 통해 열을 체크한다.대각선의 경우 행의 차이와 열의 차이가 같은 지 계산식을 통해 대..

#include #include #include #include using namespace std;bool visited[51][51];int dy[] = {0, 0, -1, 1};int dx[] = {1, -1, 0, 0};void Lift(char target, vector& storage, int n, int m){ vector> del; memset(visited, false, sizeof(visited)); for(int i=0; i>q; q.push({i, j}); visited[i][j]=1; while(!q.empty()) { ..

#include #include #include #include using namespace std;int getTime(string time){ return stoi(time.substr(0, 2)) * 60 + stoi(time.substr(3, 2));}bool cmp(vectora, vectorb){ return a[1] solution(vector> plans) { vector answer; stack>pause; sort(plans.begin(), plans.end(), cmp); for(int i=0; i=playtime) { answer.push_back(name); //과제 수행 rema..

#include #include using namespace std;int arr[4] = {10, 20, 30, 40};vectorv;int sign, price; //가입자 및 금액void dfs(vector> users, vector emoticons){ if(v.size()==emoticons.size()) //할인율 모두 결정 { int tmp_sign = 0; int tmp_price = 0; for(int i=0; i= users[i][1]) tmp_sign++; //구매 금액이 일정량 이상이면 이모티콘 가입 else tmp_price+=tmp; //아니면 매출액에 저장 } if (tm..

#include #include #include using namespace std;int solution(vector> relation) { int answer = 0; int row = relation.size(); //튜플 int col = relation[0].size(); //속성 vectorv; for(int i=1; is; for(int j=0; j 비트마스킹을 또한 조합 생성으로 풀 수 있는 문제이다.먼저 속성의 조합 경우의 수를 따져야한다.예제의 케이스를 보면 학번, 이름, 전공, 학년 4가지에 대해서의 조합이므로 2^4로 총 16가지이다.이를 비트마스킹으로 표현하면 1따라서 첫 반복문의 i는 학번, 이름, 전공, 학년의..

#include #include #include using namespace std;int solution(vector diffs, vector times, long long limit) { int l = 1, r = *max_element(diffs.begin(), diffs.end()); int answer = 0; while(l level { int prev_time = (i > 0) ? times[i - 1] : 0; total += (prev_time + times[i]) * (diffs[i] - mid); } } if(total > lim..

#include #include #include using namespace std;long long solution(int k, int d) { long long answer = 0; for(long long x = 0; x d의 범위가 크기 때문에 단순 이중 반복문으로 풀면 시간초과가 나는 문제이다.어차피 좌표의 개수를 알기 위해서는 x나 y값중 하나만 알아도 되기에 x축을 고정시키고 나머지 가능한 y값의 개수를 구하는 방식을 사용한다. 먼저 계산식에 따라 x^2+y^2따라서 이는 y^2 우리는 양수 쪽 범위만 필요하고, 최대 값을 찾아서 간격을 나누면 현재 x에 대해 가능한 y 값들을 알 수 있게 된다.따라서 y = sqrt(d^2-x^2)의 값을 먼저 구해준다. 이렇게 구한 y ..

using namespace std;#include long long solution(int w,int h) { long long answer = 1; answer = (long long)w*h - (w+h) + gcd(w, h); return answer;} 문제의 예제 기준 그림을 보면 잘려진 패턴이 4개 반복된다.이는 예제의 W(8), H(12)의 최대공약수 값이다.따라서 각 잘려진 패턴의 가로 세로 길이 또한 W/최대공약수, H/최대공약수를 한 (2, 3)이다. 해당 (2, 3) 형태의 직사각형에서 잘려나간 정사각형을 살펴보면 (2+3)-1의 형태인 것을 알 수 있다.근데 해당 패턴이 4개 즉, W와 H의 최대공약수 만큼 반복되기에 일단 아래의 식을 얻을 수 있다...

#include #include using namespace std;int arr[3][3] = {{1, 1, 1}, {5, 1, 1}, {25, 5, 1}}; //다이아, 철, 돌int getIndex(string minerals){ if(minerals[0] == 'd') return 0; else if(minerals[0] == 'i') return 1; else return 2;}void dfs(vectorpicks, vectorminerals, int idx, int total, int& answer){ if(idx >= minerals.size() || (picks[0]==0 && picks[1]==0 && picks[2]==0)) //곡괭이 모두 사용 or 광물 모두 캠..

#include #include #include using namespace std;int solution(string s) { int answer = s.size(); for(int i=1; i=2) result += to_string(cnt) + tmp; //다르면 누적된 문자열(숫자 + 문자) 저장 else result += tmp; //문자만 저장 tmp = s.substr(j, i); //새로운 문자열 시작 cnt = 1; } } // 남은 마지막 문자열 처리 if (cnt >= 2) result += to_string(cnt)..

#include #include using namespace std;void hanoi(int n, int go, int to, vector>&v){ if(n==1) //원판이 1개인 경우 (성공 케이스) { v.push_back({go, to}); return; } hanoi(n-1, go, 6-go-to, v); //n-1개의 원판을 보조(중간) 기둥으로 옮김 hanoi(1, go, to, v); //가장 큰 원판을 목표 기둥으로 옮김 hanoi(n-1, 6-go-to, to, v); //n-1개의 원판을 보조(중간) 기둥에서 목표 기둥으로 이동}vector> solution(int n) { vector> answer; ha..

#include #include#include using namespace std;int solution(vector> board){ int answer = 0; for(int i=1; i 현재 값을 기준으로 직전 3가지 값을 체크한다 (board[i-1][j-1], board[i-1][j], board[i][j-1])해당 3가지 값들의 최소값을 기준으로 + 1한 값을 현재 위치에 저장해준다.이는 모든 값이 1로 이루어진 정사각형 여부를 판별하는 것이다.만약 하나라도 0인 값이 존재하면 0+1로 1을 그대로 유지하게 된다. 이를 누적하여 더하며 이어진 정사각형 크기를 판별하고, 이렇게 저장한 값은 한 변의 길이가 된다.따라서 최종 출력은 제곱을 하여야한다.

#include #include #include #include using namespace std;int dy[] = {0, 0, 1, -1};int dx[] = {1, -1, 0, 0};bool bfs(int y, int x, vectorv){ vector> visited(5, vector(5, false)); queue> q; q.push({y, x, 0}); visited[y][x] = 1; while(!q.empty()) { auto [yy, xx, dist] = q.front(); q.pop(); if(dist == 2) continue; //맨해튼 거리 2이내만 탐색 for(..

#include #include #include using namespace std;int solution(int n, int k, vector enemy) { int answer = enemy.size(); //모든 라운드 버팀 상정 priority_queue, greater> pq; for(int i=0; i k) { n -= pq.top(); //병사 사용 pq.pop(); } if(0 > n) //병력 소진 { answer = i; break; } } return answer;} 우선순위 큐를 활용한 문제이다...