내가 정답 비율 다 낮춰준 문제 ㅎㅎ코딩을 할수록 실수가 늘어간다 역시 코딩이란..단순하게 bfs로 경로 찾아서 최단거리 구하고 이미 검은 칸은 뺴준다..bfs 함수에서 리턴하는 변수명을 계속 잘못 써서 4번이나 틀렸따.. 소스코드1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include #include #include using namespace std;char arr[2][55];int d[2][55];bool check[2][55];int dx[3] = { 1,0,-1 };int dy[3] = { 0,1,0 };int n, ans = 1e9;int bfs(int a, int b) { int ..
문제를 풀다가 가끔은 문법을 몰라서 고생하는 경우가 많다이 문제는 그냥 시물레이션을 돌리면 된다대신 다 돌지말고 %size해서 필요한 만큼만 돈다 vector의 이터레이터를 사용하면 쉽게 풀린다이 문제 풀면서 알아두면 좋은건 vector->erase를 했을 때 지워지는 것의 다음 주소를 반환하는 걸 알고있으면 편하다 소스코드123456789101112131415161718192021#include #include using namespace std;#define ll long longint n;int main() { scanf(" %d", &n); vector a(n); for (int i = 0; i
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..