1부터 N까지의 좌표가 있고 좌표 중 인덱스를 골라 그 좌표를 +1 OR -1 시킨다이 때 중복된 곳이 있다면 0을 출력 아니라면 1을 출력한다n은 크지만 m은 작기 때문에 결국 50개만 보면 된다그래서 좌표압축을하고 걍 배열에 넣고 확인했다set으로 하려다가 set에 바꿔서 넣기가 더 귀찮을 것 같아서 풀었는데풀고나니 set 이런것도 가능하다..! 역시 만능 set... 소스코드123456789101112131415161718192021222324252627282930313233343536373839#include #include #include #include using namespace std;int arr[55][55];int n, m;int getpos(int x,vector& vt) { ret..
오~~래 잡고 있던 문제다.. 8시간만에 푼듯 ㅎㅎ문제는 리프부터 루트까지 계속 1씩 증가시키며 값을 더해주고 방금 본 리프는 삭제시킨다. 그리고 새롭게 리프가 된 노드를 보며 반복한다. 루트까지~그리고 각 노드의 최종값을 출력하는 문제다 처음에 dfs 20만번이 먼저 떠올랐지만 참았다 ㅎㅎㅎ생각해보면 자식부터 쭉 올라오므로 자식의 값을 그대로 받고나의 자식 수 만큼 더하면 된다..! 그리고 나 자신을 위해 기본값은 1로한다!풀고나면 쉬운 문제.. 소스코드1234567891011121314151617181920212223242526272829303132333435363738394041#include #include #include using namespace std;#define ll long longc..
(0,0) ~ (n-1,n-1) 까지 가는 팰린드롬 경로를 찾는 문제다처음에 중복을 다 세는 줄 알고 dp로 짰는데 수가 넘 컸다..그래서 다 지우고 bfs 돌렸다가 틀렸따... 그냥 돌리면 메모리 초과다 팰린드롬이려면 대각선까지 가는것만 보면 된다그래서 대각선 정점마다 set을 만들어 (0,0)에서 출발해서 set에 넣고(n-1,n-1)에서 출발해서 set에 있는지 보면 된다 소스코드1234567891011121314151617181920212223242526272829303132333435#include #include #include #include #include using namespace std;int n;char arr[22][22];set sarr[444], ans;void f(int x,..
해석하는데 1시간 넘게 걸렸다 ㅎㅎ 1~10억 사이의 길에 P라는 위치에 높이 S 짜리 막대기를 놓는다고 생각하면 편하다. 그 후 만약 막대 사이의 거리가 막대보다 높다면 부수기 가능 N이 4000이니까 완탐을하자양쪽 방향으로 가서 탈출 가능하다면 넘기고 불가능하다면 답에 더하자 소스코드1234567891011121314151617181920212223242526#include #include using namespace std;int n;pair arr[4444];int main() { scanf(" %d", &n); for (int i = 0; i
B E S I E G O M 7가지 문자에 최대 20개의 가중치가 들어온다그 때 (B+E+S+S+I+E)*(G+O+E+S)*(M+O+O)가 짝수인 경우의 수를 찾는 문제다 처음에 생각을 하고 한심한 방법같아서 코딩을 안하다가설마하고 해봤는데 맞았다..!근데 맞는 방법인지는 모르겠따 먼저 3개의 곱이 짝수라는 얘기는 하나만 짝수면 된다는 얘기다하나만 짝수면 곱했을 때 무조건 짝수다 그래서 한덩어리씩 보며 짝수가 되는 경우의 수를 찾았다1) BESSIE에서는 E와 S가 짝수개 이므로 B+I가 짝수인 경우만 세면 된다2) GOES 에서는 B+I가 홀수인 경우 * (G+O+E+S)가 짝수인 경우를 센다3) MOO 에서는 (B+I 홀수) * (G+O+E+S 홀수) *(M이 홀수)를 센다! 이렇게 더하면 답나온다!..
영어문제는 가끔 알고리즘보다 영어가 어려워서 틀린다문제 자체는 트라이 기본문제 boggle처럼 생겼다 주어지는 문자열에서 MOO를 찾을건데 M과 O를 다른 문자로 대체 가능하고 그 때의 최대값을 출력해야한다!근데 여기서 자기 자신으로는 대체가 불가능하다즉 M-> M || O->O라면 불가능 한 경우다 이걸 처음에 발견 못해서 틀렸다 크기가 작으므로 26 X 26 X 50 X 50으로 풀면 충분히 들어온다~ 소스코드12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include #include using namespace std;char board[55][55];int n, m,ans;int dx[8] = ..
정말 평범한 문제다평범하게 아는대로 냅색을 하면 풀린다근데 잘 푼 사람들보니까 나랑 메모리가 20배는 차이난다..!1차dp로 풀었던데 좀 봐야겠다 ㅎㅎ 내가 푼 방식은가방을 1~N까지 보며 max(선택 O, 선택 X) 를 보며 최대값을 찾았다 소소코드123456789101112131415161718192021#include #include #include using namespace std;int d[111][111111];int w[111], v[111];int n, k;int go(int pos, int sum) { if (sum
a라는 수를 n번 턴동안 xor 시켜서 b로 가면 된다문제가 참 생각만 한다면 쉽게 풀 수 있다 생각해보면 모든수가 있기 때문에 a에서 b로 xor 한번만에 무조건 갈수있다그럼 n번의 경우동안 한번 b로갈 경우 1번 미리 빼두자n-1번 동안은 내맘대로 해도 된다 그리고 갈 수 있는 경우는 계속 2^31이 된다(모든 수로 가는게 가능)결국 답은 2^31^(n-1)이 된다! lgN만에 구해주자~! 소스코드1234567891011121314151617181920#include #include #include using namespace std;#define ll long longll a, b, n;ll mod = 1e9 + 7;ll mypow(ll x, ll y) { if (!y) return 1; if (y..
문제를 요약해보면 세개의 수를 정했을 때중위값과 평균값의 차이가 최대가 되도록 하고 그 값의 3배를 출력하면 된다! 우리는 수학적으로 문제에 접근해야 한다세 수를 a,b,c라고 하자 (a a를 고정시키기 고정시키고 돌면 최대 20만번이면 확인가능하다! 소스코드12345678910111213141516#include #include #include using namespace std;#define ll long longll n, arr[100010]; int main() { scanf(" %lld", &n); for (int i = 0; i
내리 갈굼 2번째 문제이다이번엔 쿼리를 날려주는데 한 노드의 상태를 출력해야한다트리를 세그먼트 트리로 만들 수 있다면lazy를 써서 쉽게 풀 수 있다! 소스코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778#include #include #include #include using namespace std;const int MAXN = 1e5 + 5;int p[MAXN], num[MAXN], cnum[MAXN],cnt;bool check[MAXN];vector Graph;int dfs(int ..