고동치는고동

123456789101112131415161718#include #include using namespace std; int main(void) { int n, cnt = 0; cin >> n; for (int i = 1; i > a; if (a != i) { cnt++; } } cout

생각해보면 간단하다.중앙의 동전을 원하는 상태로 바꿔놓고 그 동전은 그대로 놔두고 좌우로 뻗어나가면서 다른 동전들도 똑같이 만들어 주면 된다.마지막에는 끝 동전 하나만 뒤집을 수 있으므로 항상 모든 수들의 절댓값의 총합 (+,-)로 뒤집을 수 있다.따라서 최대를 구하기 위해서는 입력되는 동전의 가치의 절댓값을 모두 더하면 된다. 1234567891011121314151617#include #include using namespace std; int main(void) { int n; long long sum = 0; cin >> n; for (int i = 0; i > a; sum += abs(a); } cout

처음에 문제를 잘못 이해해서 이긴 사람은 자신이 낸 패를 그대로 계속 내는 문제인 줄 알았다.그래서 코드를 필요한 부분만 수정하느라 지저분해졌다.가위바위보의 승패를 쉽게 판단하기 위해 게임의 결과가 같으면 두 손패를 뺀 뒤 3으로 나눈 나머지가 같음을 이용했다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include #define mod 1000000009using namespace std; int arr[305];int brr[305]; int main(void) { int n, ans = 1, cnt = 0; cin >> n; for (int i = 0; i > arr..

간단하게 q번째 메세지 아래 있는 사람들은 전부 q메세지를 읽었다. 추가로,q번째 메세지를 n명이 읽었다고 하면 그 위의 n명이 읽은 메세지도 q메세지를 읽었음을 알 수 있다. (카톡에서 눈치싸움 하다보면 알게된다.) 모든 사람이 봤을 경우 -1을 출력하는 것과 A는 대상에서 제외시키는 것만 유의하면 된다. 123456789101112131415161718192021222324252627282930313233343536373839#include #define mod 1000000009using namespace std; int arr[10005];int brr[10005];bool chk[30]; int main(void) { int n, k, q; cin >> n >> k >> q; for (int i..

2차원 격자에서 블록 순서를 주었을 때 좌표를 구하면 된다. 123456789101112#include #define mod 1000000009using namespace std; int main(void) { int n, m, k; cin >> n >> m >> k; cout

small 에서 범위만 늘려주고 mod연산만 추가하면 된다. 123456789101112131415161718192021#include #define mod 1000000009using namespace std; int main(void) { int n; long long dp[33335][3]; cin >> n; dp[1][0] = 0; dp[1][1] = 1; dp[1][2] = 1; for (int i = 2; i

간단한 dp문제이다.3의 배수는 각 자리의 합이 3의 배수이다.dp[i][j] 는 i의 자릿수 중 모든 자릿수를 더한 뒤 3으로 나눈 나머지가 j가 되는 수의 경우의 수 1234567891011121314151617181920#include using namespace std; int main(void) { int n; int dp[1005][3]; cin >> n; dp[1][0] = 0; dp[1][1] = 1; dp[1][2] = 1; for (int i = 2; i

처음에 단순 BFS로 풀었는데 터졌다.위상정렬을 써야 한다고 한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include #include #include #define n_ 1000+5using namespace std; vector v[n_];int arr[n_];int ans[n_];int cnt[n_]; void solve(int now){ cnt[now]--; for (int i : v[now]){ ans[i] = max(ans[i], ans[now] + arr[now]); cnt[i]--; if (!cnt[i]){ solve(i); } }} int main(..

시간초과가 떠서 꽤 오래걸렸다.초기에는 가방에 중심을 두고 작은 순서대로 하나씩 봐가면서 가능한 보석중 가장 가치가 큰 보석을 넣는 방법을 생각했다.어처피 뒤에오는 더 큰 가방에서는 앞에 온 작은 가방에 넣을 보석을 넣을 수 있기 때문에 작은 가방은 자신의 입장에서 최적의 보석을 고르면 된다. 근데 가장 가치가 큰 보석을 찾는 방법을 for문으로 N번 돌렸더니 시간 복잡도가 총 O(NK)가 되어 시간초과가 떴다. 따라서 힙구조 우선순위 큐를 사용해서 가장 가치가 큰 보석 찾는 시간을 단축했다. 가방의 크기가 커져서 넣을 수 있는 보석이 더 많아지면 그 보석들을 우선순위 큐에 넣어준다. 그리고 매 가방마다 가장 위의 요소를 pop해서 ans에 더하면 된다. 참고로 우선순위 큐에 들어있는 보석들은 i번째 가..

처음에 DP라는 말에 쉬운줄 알았지만쿠폰과 쉬는 날을 보고 멘붕이 왔다.오래 고민하다가 머릿속에서 꼬여서 포기하고 검색했다. http://wookje.dance/2017/03/06/boj-13302-%EB%A6%AC%EC%A1%B0%ED%8A%B8/ http://wookje.dance/2017/03/06/boj-13302-%EB%A6%AC%EC%A1%B0%ED%8A%B8/ 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include #include #define n_ 106#define INF 0x7fffffffusing namespace std; int n, m;int..