돌이 코딩하는 방

solved 기준 문자열을 너무 안풀었고, 문자열 관련 기초 코딩능력이 딸리는 것 같아서 아래와 같이 검색한 랜덤 문제를 푸려고 한다. 계속 푸는 대로 업데이트 할 예정이다. BOJ 17413 단어 뒤집기 제발 문제 좀 읽자. 1. 전체 뒤집은면 되는 줄 알고 reverse가 끝인줄 알았다. 2. 단어별로 뒤집는 것 인줄 몰랐다. 3. 자잘한 코딩 실수들. 정신좀 차리자. 대회면 망했다. 그래도 줄 입력이 getline(cin,s); 인것은 기억해냈다. 풀이는 입력 종류별로 케이스를 나눠서 뒤집어야 하는 것들은 스택에 담아두면 끝. 닥히 어렵지 않다. 더보기 #include using namespace std; typedef long long int ll; string s; string s2; stack..

문제 링크 : https://www.acmicpc.net/problem/1028 문제 풀이 다이아몬드는 4개의 선분으로 이루어진다. 정확히 맞물리는 4개의 길이가 같은 대각선을 찾으면 된다. 어떤 위치로 부터 k개의 연속된 1이 대각선 방향으로 있으면 k 이하의 임의의 길이의 대각선을 찾을 수 있다는 것이다. 따라서 우리는 모든 위치에 대해서 4개의 방향으로 각각 어디까지 1이 이어져 있는지를 알고 있어야 한다. 따라서 다음과 같이 DP 값을 정의할 수 있다. ld[i] = 왼쪽 아래로 이어져 있는 1의 개수, rd[i] = 오른쪽 아래로 이어져 있는 1의 개수, lu[i] = 왼쪽 위로 이어져 있는 1의 개수, ru[i] = 오른쪽 위로 이어져 있는 1의 개수. 이는 주어진 맵을 스캔하는 과정에서 $O..

문제 링크 : https://www.acmicpc.net/problem/17834 문제 풀이 문제를 보자마자 홀짝성을 생각할 수 있다. 다시 말하자면 주어진 그래프를 2가지 색으로 칠할수 있는지를 물어보는 문제이다. 만약 주어진 그래프를 2가지 색으로 칠할 수 있다면, 두 동물의 시작 색깔이 다르면 영원히 잡을 수 없게 되기 때문이다. 주어진 그래프를 두 가지 색으로 칠할 수 있는지를 확인해 보자. 이는 dfs 한 번으로 쉽게 확인할 수 있다. dfs를 기본적으로 돌면서 두 가지 색을 번갈아가면서 칠해준다. dfs를 돌 다 보면 이미 방문한 정점을 거를때가 있는데, 거르기 전에 현재 정점과 다른 색으로 칠해져 있는지를 확인해주면 된다. 만약 같은 색이라면 두 가지 색으로 칠할 수 없는 그래프이다. 하지만..

문제 링크 : https://www.acmicpc.net/problem/2924 문제 풀이 주어진 수열의 i번째 값을 A[i]라고 하자. 우리는 $C\leq k\leq N-D$ 인 k들에 대해서 모든 A[A[A[A[A[...A[k].]]]]=k가 되는 최소 횟수를 찾아야 한다. 당연히 B번을 돌려보는 것은 문제를 해결할 수 있는 방법이 아니다. 최소 횟수를 m이라고 하면 답은 (B회까지 처음과 같은 형태의 개수 - A-1회 까지 처음과 같은 형태의 개수) 이기 때문에 (b+m-1)/m-(a+m-2)/m의 형태가 된다. 따라서 m을 구하기만 하면 된다. 각 k에 대해서 다시 k로 돌아오는데 까지 걸리는 횟수를 알게 되면 $C\leq k\leq N-D$ 인 k들에 대해서 그 횟수들을 모두 lcm 취해주면 모..

문제 링크 : https://www.acmicpc.net/problem/15907 문제 설명 n개의 수들 중에서 최대한 많은 수를 포함하는 ax+b (a는 2이상의 정수, b,x 는 정수) 꼴을 찾아내야 한다. 이때 그 꼴으로 표현할 수 있는 수의 갯수를 출력하면 된다. 문제 풀이 ax+b 꼴에 최대한 많은 수를 포함시켜야 한다. 생각을 해보자. 2로 나눈 나머지로 수들을 분리하는것이 무조건 4,6,8,10..등으로 수를 분리하는 것보다 이득이다. 이는 3,4,5... 등에 대해서도 모두 적용되는 논리이다. i로 분리해서 확인하면 ki꼴의 수에 대해서는 확인하지 않는 것이 이득이다. 이러면 무엇이 떠오르는가? 당연히 소수이다. 즉, 소수에 대해서만 판별을 하면 된다는 것이다. 2000000만까지의 모든 ..

문제 링크 : https://www.acmicpc.net/problem/15311 문제 풀이 친구가 재밌는 문제라고 풀어보라고 했던 문제가 백준에, 심지어는 나는코더다 2017 송년대회에 있을줄은 몰랐다. 아이디어성 문제이다. 루트, 버킷에 익숙한 사람은 좀 더 쉽게 보일 수도 있다. 사실 풀이를 어떻게 써야할지 모르겠다. 그래도 최대한 사고의 흐름을 써보려고 한다. 맨 처음에는 이진법을 생각했다. 모든 값을 다 표기하는데 이진법만큼 쉽고 간단한 방법이 떠오르지 않았다. 하지만 이진법은 자릿수가 계속 올라간다는 문제가 있었다. 1 2 1 4 2 1 뭐 이런식으로 할 수도 없었고, 자릿수가 많은 표기법은 좋지 못하다는 생각을 했다. 2000과 1000000을 계속 생각해봤다. $n^k=1000000$이고 ..

문제 링크 : https://www.acmicpc.net/problem/1395 문제 태그 더보기 Segment Tree Lazy Propagation 문제 풀이 문제를 보자. 거의 Segment Tree Lazy Propagation 연습문제라고 해도 될 정도로 기본적인 연산을 요구하고 있다. 구간의 값을 바꾸는 연산과 구간의 값을 구하는 연산. 값을 바꾸는 연산은 구간 내의 1을 모두 0으로 바꾸고 0을 모두 1로 바꾸는 연산이다. 이때 기존의 s~e 구간을 담당하고 있는 구간의 값이 val이라면 연산을 한 후 새로운 값은 e-s+1-val 로 쉽게 구할 수 있다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 2..

문제 링크 : https://www.acmicpc.net/problem/17167 문제 설명 두 숫자 a,b 가 주어져 있을 때, 5000번 이하의 a+=b, a+=a, b+=b, b+=a의 4가지 행동을 통해서 a와 b를 똑같게 만들 것이다. 이때 걸리는 횟수와 그 방법을 출력하시오. 문제 풀이 일단 범위를 줄이는 데 집중을 해보자. 3,9로 수를 시작하는 것과, 1,3으로 수를 시작하는 것은 다른 결과가 나올까? 라는 질문으로 시작을 하게 되면 아니라는 결론이 나오게 된다. 좀 더 확장시켜서 생각을 해보면 항상 a,b를 같게 만드는 일련의 행동들은 c=gcd(a,b)인 c에 대해서 a/c, b/c를 같게 만들 수 있다. 물론 반대도 성립한다. a+=a는 a를 두 배 시키는 것과 동치이다. 따라서 b가..

문제 링크 : https://www.acmicpc.net/problem/2988 (P3) 문제 풀이 2번째 줄에 등장하지 않은 수나, 3번째 줄에 등장하지 않은 수의 값이 첫번째 줄에 쓰여있으면 그 줄은 절대로 선택될 수 없다. 그 줄을 지우게 되면 이로 인해서 또 2번째 줄이나 3번째 줄에 등장하지 않는 수가 생길 것이다. 그러면 또 그 수가 첫번째 줄에 적혀있는 줄을 지운다. 이 과정을 반복하면 된다. 더이상 이 과정을 진행하지 않는다는 것은 첫번째 줄에는 있는데, 두번째 줄이나 세번째 줄에는 없는 수는 없다. 이때 각 줄에 쓰인 수의 갯수는 같으므로, 각 줄에 대해서 쓰여있는 수들의 집합은 셋이 모두 동일할 수 밖에 없게 된다. 이는 문제 해결 조건과 정확히 일치하다. - 코포에 나올법한 문제. 그..

※ 이 문제를 풀기 전에는 이 문제 를 미리 풀고 오시는 것을 추천드립니다. ※ 이 포스팅을 보시기 전에는 이 포스팅 을 미리 보고 오시는 것을 추천드립니다. ※ 이 포스팅은 BOJ 14435 놀이기구 2의 풀이를 모두 알고 있다고 가정하고 작성되어 있습니다. 문제 링크 : https://www.acmicpc.net/problem/18473 (R5) 문제 태그 더보기 union & find, smaller to larger 문제 풀이 일단 가장 간단하게 시간복잡도에 상관없이 문제를 푸는 방법에 대해서 생각을 해보자. 1부터 m번까지의 간선을 모두 보고 되는 간선을 체크하자. 당연하게도 우리는 가능한 간선들이 바뀔 때마다 계속해서 번호가 가장 간선을 선택해야하므로, 수를 추가하거나 빼면서 이를 관리하고, ..