The Way

저번 주에 이어서 또 도전... 저번보다 문제가 약간 별로인 것 같다.저번보다 못한 6문제를 풀었다. 하나는 풀이를 알았는데 시간이 없었고, 하나는 내가 끝끝내 예외를 못찾아서 틀렸으니 조금 더 실력이 있었으면 8문제는 거뜬했을 듯. 내가 1문제를 푼거로 봐서 내가 못한 것 같다.. 근데 나한테 배정된 A~D가 솔직히 좀 어려워서 털릴 만 했다... E번(637C) - Promocodes with MistakesN군이 후다닥 풀었다.6자리의 n개의 이벤트 코드가 있는데, 코드를 칠 때 k자리를 잘못 칠 수 있다. 이 때 모든 코드를 구별하기 위한 최대 k를 구하는 문제.엄청 쉬운데, 두 코드가 p자리가 서로 다르면, (p - 1) / 2개 이하를 잘못 쳐야 둘을 구별할 수 있다. 모든 쌍에 대해 반복하면..

방학 중에 UCPC를 서울대 D군, N군과 같이 나가게 되면서 한 주에 한번씩 모여서 팀연습을 하기로 했다.어제는 첫 번째 팀연습을 했다. 연습은 Road To Grandmaster라는, hyunuk님이 잘 만들어주신 4시간, 12문제짜리 문제셋을 가지고 진행하기로 했다.문제 난이도는 다 1700~2400점 사이의 문제들이라 다 풀 만 한 문제들이다. 엄청난 꿀문제도 없고, 그렇다고 아예 못 풀 문제는 없는 수준의 문제들이다. 처음이라 약간 방황해서 예상보다 약간 성적이 좋지 않지만, 그래도 기존까지는 팀대회에서 뭔가 나 혼자만 푸는 기분이었는데 이번에는 다 같이 푸는 것 같아서 좋았다. 무엇보다 우리 팀에는 빛나는 오렌지가 있기 때문에.. N군 A~D, D군 E~H, 나 I~L을 읽기로 하고 virtu..

자연수 n이 주어질 때, n을 서로 다른 피보나치 수의 합으로 나타내는 문제이다. 이 때 사용하는 피보나치 수의 갯수는 최소가 되어야 한다. 풀이는 생각보다 간단하다. n보다 같거나 작은 피보나치 수 중 가장 큰 피보나치 수를 사용하고, 이를 반복하면 된다. 가령 n=100이면 89를 사용하고, 남은 11에 대해서 8을 사용하고, 또 남은 3에 대해 3을 사용하면 된다. 답을 때려맞추기는 상당히 쉬운 문제이지만, 왜 그게 성립하는지 증명하기는 상당히 까다롭다. 과연 이 방법이 왜 최적의 해를 가져올까? 예시와 함께 증명을 해보자. 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... 89~143까지의 숫자에 대해 생각을 해보자. i) 임의의 수에 대해, n보다 같거나 작은 피보나..

자기 전에 한 문제만 풀고 자려고 했는데, 이 문제 때문에 잠을 못잤다. 케이스가 상당히 극악인 문제이다. 문제는 아주 심플하다. 방정식 Ax + By + C = 0의 정수해의 개수 구하기이다. x와 y는 x1 ≤ x ≤ x2, y1 ≤ y ≤ y2를 만족해야 한다. 각 수의 범위는 -10^8 ~ 10^8이다. 일단 수의 범위가 상당히 크기 때문에 직접 다 해보는 알고리즘은 시간초과가 뜰 가능성이 농후하다. 케이스를 나누어가며 접근해보자. i) A와 B 둘 다 0인 경우 가장 쉬운 경우이다. C = 0이면 모든 해가 정답이고, C ≠ 0이면 해가 없다. ii) A와 B 둘 중 하나만 0인 경우 편의상 A = 0, B ≠ 0이라 해보자. 그럴 경우 방정식은 By + C = 0이 된다. C가 B로 나누어 떨..

소수 컬렉션을 풀어보았다. 백준 1456: 거의 소수범위가 10^14이다. 다행히 N제곱 꼴인 경우를 물어봤으므로, 10^7까지의 소수를 미리 구해놓고, 2제곱/3제곱/...을 잘 세어보면 된다.코드의 생명은 오버플로우 관리. 예를 들어서, 소수 p를 곱해가면서 b보다 커질 때까지 한다고 하면, b가 10^14라고 하면 10^7보다 약간 작은 소수에 대해서는 10^21 정도까지 가게 되는데, 이는 long long 범위도 넘어선다. 적당히 max값을 잡는 것이 이롭다. #include #define N 10000005 using namespace std; bool notprime[N]; int main() { for (int i = 2; i * i < N; ++i) { if (!notprime[i]) {..

꽤 쉬운 것 같길래 공부를 시작하기 전 가볍게 워밍업으로 풀어보았다. 백준 17173번: 배수들의 합N이 작아서 그냥 다 더해주면 된다. 생략. #include #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n, m, t; cin >> n >> m; vector arr(n + 1, 0); while (m--) { cin >> t; for (int i = t; i > m; int ans = 0; while (n) { ans += n; n /= m; } cout n; cout = 'A' && c = 'a' && c > a >> b >> c; int p, q, r; p = a; q = 2 * b * c; r..

백준에는 가끔 경이로운 문제들이 있다.재능이 많은 사람들이 그 재능을 발산할 곳을 찾다 못해 백준 문제에 그 정수를 담아놓는 듯한 기분이다.구데기컵의 이 문제도 그러하다. 본격적인 채굴 문제... 문제의 기본적인 원리는 비트코인의 그것을 이용한다.비트코인에 조금이나마 관심이 있는 사람이라면 비트코인이 hash를 쓴다는 것 정도는 알고있을 것이다. 하지만 사실 hash를 직접 써 볼 기회가 그리 많지는 않다. 이 문제는 그런 의미에서 요즘 각광받는 블록체인 기술의 맛보기라도 볼 수 있다는 점에서도 아주 좋은 문제이다. 배경 지식을 아주 간단하게만 설명하면, 비트코인은 블록 전체를 sha-256이라는 해시 알고리즘을 통해 hash를 돌려서 hash값이 특정 숫자 이하가 나오도록 하며,블록에는 거래정보 / 직..

인기 문제에 있는 꿀문제만 조져보았다. 백준 15637번: Lotto구데기컵스럽게 이상한 문제인데 쉬운 편.https://dhlottery.co.kr/gameResult.do?method=byWin링크 아래쪽에서 친절하게 ~회부터 ~회까지 당첨번호를 엑셀로 다운받을 수 있다.코드는 굳이 첨부하지 않는다. 백준 17202번: 핸드폰 번호 궁합어릴 적에 한번쯤은 해보았을 듯한 이름 궁합과 비슷하다.틀리기가 더 힘든 문제. #include using namespace std; int main() { char num1[9], num2[9]; int arr[16]; cin >> num1 >> num2; for (int i = 0; i < 8; ++i) { arr[i * 2] = num1[i] - '0'; arr[..

오랜만에 백준을 풀어보았다. 감이 좀 떨어진 것이 느껴진다.오랜만에 codeforces도 해보았다. Div3이었는데도 참교육당했다. 백준 17144번: 미세먼지 안녕!정직한 구현 문제. 미세먼지는 상하좌우 4방향으로 확산이 일어나고, 공기청정기 바람의 경로에 있는 먼지들은 바람의 방향대로 한 칸씩 이동한다.공기청정기 바람의 방향 때문에 조금 노가다가 심하다. 더 짧게 짤 수는 있겠지만 빨리 짜는 것과 적당히 밸런스를 맞추어야 한다. #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int r, c, t; cin >> r >> c >> t; int air[51][51] = {}; int pos1 = -1, pos2..

다이나믹 프로그래밍 위주로 한 번 풀어보았다. 백준 2618번: 경찰차 경찰창의 위치와 각 위치일 때 그 위치가 될 때까지 이동한 거리의 최솟값을 저장해놓으면 된다. 나는 빡대가리같이 map을 써서 코드를 짰다. 굉장히 똥코드지만.. 뭐 통과만 하면 됐지 정석 방법은 각 위치를 1~1000번 번호를 붙여준 뒤 2차원 배열에 저장하는 방법이다. 문제가 치사하게 경로까지 출력해야 하기 때문에 아마 거리, 직전 위치 2가지는 저장해야 한다. #include #include #include using namespace std; typedef pair ii; int dist(int a, int b) { return abs(a / 10000 - b / 10000) + abs(a % 10000 - b % 10000)..