문제 요약 및 풀이 3878번: 점 분리 사실 1년 전에 푼 문제다. 기하 알고리즘을 갑자기 한번 쓰윽 볼까? 하고 다시 핀 문제인데, 1년동안 회사일을 하면서 다 까먹었음을 느꼈다. 컨벡스헐의 ㅋ 자도 못 구현하고 있었다. 그래서, 그냥 1년 전의 나의 코드를 가져와서 코드를 리팩토링하면서, 다시 공부했다. 풀이 설명은 코드에 주석으로 담...
[BOJ] 22351 수학은 체육과목 입니다 3
문제 요약 및 풀이 22351번: 수학은 체육과목 입니다 3 시작 지점을 특정하는 방법이 중요하다. 시작 지점을 임의의 수로 생각하는게 아니라, 특정 길이의 수로 보고 탐색하면 빠르고, 간단하게 처리할 수 있다. 풀이 코드 s = input() for start_len in range(1, len(s)+1): s2 = s[:start_le...
[BOJ] 1359 복권
문제 요약 및 풀이 1359번: 복권 python itertools에는 너무나 좋은 것이 많다. ㅎㅎ 이 문제는 그냥 모든 경우를 탐색해도 된다. 그냥 빠르게 긁어버리자. (N,M이 8보다 작거나 같다. 경우 의 수가 8C4 정도가 최대다. 충분히 다 탐색할 수 있다.) 풀이 코드 from itertools import combinations...
[BOJ] 20443 배드민턴 대회
문제 요약 및 풀이 20443번: 배드민턴 대회 문제를 딱 보자 마다, 어디선가 봤던 건데… 하고 망설였는데, 결론적으로는 교란순열이었다. (맨날 점화식 까먹는 것 같다.) i) 교란순열의 i번째 항을 d[i]라 하자. ii) 주어진 수가 4의 배수 인 경우, d[i]를 반환한다. iii) 주어진 수가 4의 배수가 아닌 경우, combinati...
[BOJ] 20551 Sort 마스터 배지훈의 후계자
문제 요약 및 풀이 20551번: Sort 마스터 배지훈의 후계자 이진탐색을 잘 하자. 풀이 코드 #include <bits/stdc++.h> #define for1(s,n) for(int i=s; i<n; i++) using namespace std; int N, M, a; int ar[220000]; int main(...
[BOJ] 21966 (중략)
문제 요약 및 풀이 21966번: (중략) 간단한 구현 문제다. 심지어 굉장히 테케가 친절한데, 아래 2번째 테케에서 앞/뒤 11글자를 제외한 나머지 부분이 Man. 으로 한 문장안에 포함된다고 한다. 따라서, 앞 11글자 / 뒤 12 글자(11글자가 아니다라는 것)를 제외하고 그 안에 . 이 있는 경우, 앞 뒤 내용이 서로 다른 문장에 포함...
[BOJ] 1503 세 수 고르기
문제 요약 및 풀이 1503번: 세 수 고르기 너무 많이 틀려가며 풀었다 ㅠ 일단 푸는 방법은 브루트 포스, 다 긁어버리면 된다. 하지만 무작정 다 긁으면 TLE 난다. N이 최대 1000이고, 이것보다 조금은 큰 범위로 세제곱만큼해서 긁어야 하는데, 이걸 다 긁으면? 가뿐히 1억을 넘긴다. 따라서 몇가지 스킵 조건을 걸어서, TLE가...
[BOJ] 1484 다이어트
문제 요약 및 풀이 1484번: 다이어트 일단, 나이브하게 풀었다. ㅋㅋㅋ 풀이 코드 몇가지 간단한 생각을 하고, 나이브하게 다 긁었다. 특정 수가 제곱인지 확인하는 건, sqrt 씌우고 다시 곱해보면 된다. 어떤 수 i가 순서대로 증가할 때, \(i*i - (i-1)*(i-1) > g\) 되는 순간, 더이상 i 를 늘리면서 확...
[BOJ] 1253 좋다
문제 요약 및 풀이 1253번: 좋다 문제 조건은 심플하다. 어떤 수가 다른 수 2개로 구성되면 이는 좋은 수 이다. 좋은수 a가 있다면, 주어진 수 중 a를 모두 카운트해야 한다. 근데, 만약 그냥 단순하게 이중 반복문으로 처리한다면, WA를 신랄하게 맞을거다. d = {} # 각각 요소가 몇개 있는지 저장된 해쉬 ... an...
[BOJ] 1083 소트
문제 요약 및 풀이 1083번: 소트 처음에 어? 그냥 앞에서부터 버블 소트처럼 하면 되는거 아니야? 라는 단순한 생각을 했고, 그냥 제출했는데 바로 WA를 받았다. 골드가 그렇게 간단하지는 않죠? (ㅋㅋㅋ) 바로 떠오른 반례는 이거다 5 1 2 3 4 5 4 앞서 말한 풀이로는 2 3 4 5 1이 나오는데, 사실 답은 5 1 2...