#include #include using namespace std;long long solution(int cap, int n, vector deliveries, vector pickups) { long long answer = 0; long long d = 0, p = 0; for(int i=n-1; i>=0; i--) { int cnt = 0; d -= deliveries[i]; p -= pickups[i]; while(d 그리디하게 접근하여 풀 수 있는 문제이다.배달과 수거에 대한 변수를 따로 두고, 끝에서부터 배달해야 하는 값과 수거해야 하는 값을 체크한다.이후 반복문을 통해 cap의 수치만큼 더해가며,..
#include #include #include #include #include using namespace std;typedef long long ll;vector solution(vector> line) { set> points; //중복 없이 저장 ll minX = 1e18, maxX = -1e18, minY = 1e18, maxY = -1e18; for (int i = 0; i answer(h, string(w, '.')); //.으로 채우기 for (auto i : points) //해당 좌표만 * 처리 { ll r = maxY - i.second; ll c = i.first - minX; answer[r][c] = '..
#include #include #include using namespace std;int solution(int h1, int m1, int s1, int h2, int m2, int s2) { int answer = 0; int sTime = h1 * 3600 + m1 * 60 + s1; int eTime = h2 * 3600 + m2 * 60 + s2; if (sTime == 0 || sTime == 12 * 3600) answer++; while (sTime = hNext) answer++; if (sCur = mNext) answer++; if (abs(sNext - mNext) 주어진 시, 분, 초 에 대해서 시작 시간과 끝 시간 값을 따로..
문제링크 : https://www.acmicpc.net/problem/9009#include using namespace std;const int MOD = 1000000007;int arr[45];int main() { int T; cin >> T; arr[0]=0; arr[1]=1; for(int i=2; i> n; vectorv; for(int i=44; i>=1; i--) { if(n 우선 피보나치 배열의 값을 채워준다.문제의 조건에 따라 n의 범위가 1,000,000,000까지 가능하므로, 44까지만 값을 채워준다. (45 : 1,134,903,170) 이후로는 뒤에서부터 체크하며 입력받은 n에 대해 arr[i..
#include #include #include using namespace std;bool check(char op, int n, int diff){ if(op == '=') return n == diff; else if(op == '>') return diff > n; else if(op == ' diff; return 0;}int solution(int n, vector data) { int answer = 0; string s = "ACFJMNRT"; sort(s.begin(), s.end()); do { bool flag = 1; for(auto i : data) { int idx1 ..
#include #include using namespace std;int dx[] = {1, -1, 0, 0};int dy[] = {0, 0, 1, -1};bool visited[101][101];int cnt;void dfs(int m, int n, int x, int y, vector>& picture, int target){ visited[x][y] = 1; cnt++; for(int i=0; i=m || ny >=n) continue; if(visited[nx][ny] || picture[nx][ny] != target) continue; dfs(m, n, nx, ny, picture, target); } }// 전역 변수를 정의할 경우..
#include #include #include using namespace std;map>, int>m; //특정 시간에 특정 위치를 지난 사람 카운트int solution(vector> points, vector> routes) { int answer = 0; for(auto route : routes) { int time = 0; for(int i=0; i 0 ? 1 : -1; m[{time++, {x, y}}]++; } while(y!=points[e][1]) { y += points[e][1] - y > 0 ? 1..
#include #include #include using namespace std;bool check(long long idx, int n){ if(n == 0) return 1; long long size = pow(5, n); //5제곱씩 증가 if(idx/(size/5) == 2) return 0; //인덱스가 가운데인지 체크 (무조건 0) return check(idx%(size/5), n-1);}int solution(int n, long long l, long long r) { int answer = 0; for(long long i=l-1; i 먼저 규칙을 살펴보면 가운데는 무조건 0인 것을 알 수 있다.따라서 이를 토대로 재귀를 통해 ..
문제링크 : https://www.acmicpc.net/problem/15353#include using namespace std;const int MOD = 1000000007;int arr[10001];int main() { string s1, s2; cin >> s1 >> s2; // 두 문자열의 길이를 맞추기 if (s1.size() = 0; i--) { int sum = (s1[i] - '0') + (s2[i] - '0') + carry; carry = sum / 10; sum %= 10; result += sum + '0'; } // 마지막 올림 체크 if (carry) result += carry..
#include #include #include using namespace std;const int INF = 99999;int solution(vector> info, int n, int m) { int size = info.size(); vector> dp(size+1, vector(m, INF)); dp[0][0] = 0; for (int i = 0; i 그리디하게 접근하여 풀 수 있는 문제이다.먼저 정렬을 a가 맡으면 손해인 물건이 우선시되게 정렬해준다.기본적으로 각 흔적의 차이를 계산하여, a가 훔쳤을 때 차이가 더 큰 값 우선으로 정렬하게 된다.차이가 아에 같은 경우도 발생할 수 있는데, 이는 비율을 계산하여 정렬해준다. 이후에는 간단하게 b가 가능한 경우 b부터 누적..
문제링크 : https://www.acmicpc.net/problem/32981#include using namespace std;const int MOD = 1000000007;long long cal(long long base, long long exp, int mod) { long long result = 1; long long cur = base % mod; while (exp > 0) { if (exp%2) result = (result * cur) % mod; cur = (cur * cur) % mod; exp /=2; } return result;}int main() { ios::sync_with_stdio(fals..
문제링크 : https://www.acmicpc.net/problem/12871#include using namespace std;const int MOD = 1000000007;int main() { string s1, s2; cin >> s1 >> s2; string tmp1="", tmp2=""; for(int i=0; i 서로의 문자열 길이가 같은 상태에서 체크하면 되니, 다른 문자열 길이에 따라 현재 문자열을 그만큼 반복해준다.이렇게 구한 길이가 같은 문자열들에 대해 같은 지 여부 체크해주면 된다.
#include #include #include using namespace std;int n, m;bool visited[501][501][4];//상, 우, 하, 좌int dx[4] = {-1, 0, 1, 0};int dy[4] = {0, 1, 0, -1};int dfs(int x, int y, int dir, vectorv){ int cnt = 0; while(!visited[x][y][dir]) { cnt++; visited[x][y][dir]=1; if(v[x][y]=='L') dir = (dir+3)%4; //좌회전 else if(v[x][y]=='R') dir = (dir+1)%4; //우회전 ..
#include #include #include using namespace std;int maxdiff = 0;vector answer;void dfs(int idx, int arrows, vector lion, vector apeach) { //마지막 과녁까지 탐색했거나 화살을 다 쓴 경우 if (idx == 11 || arrows == 0) { if (arrows > 0) lion[10] += arrows; //남은 화살 0점에 넣기 int lionScore = 0, apeachScore = 0; for (int i = 0; i apeach[i]) lionScore += 10 - i; //라이언 점수 else apeachS..
#include #include using namespace std;int solution(string name) { int answer = 0; int len = name.size(); for (auto c : name) //다음 또는 이전 알파벳 { answer += min(c - 'A', 'Z' - c + 1); } // 기본 커서 이동 수 int move = len - 1; for (int i = 0; i 먼저 알파벳 변경 같은 경우는 간단하게 현재 알파벳에 따라 앞에서부터 바꾸는게 빠른지, 뒤에서부터 바꾸는게 빠른지 선택한다. 이제 커서 이동 수이다.기본적인 최대 커서 이동 수는 처음부터 오른쪽으로 쭉 이동하는 name...