이건 나이스가 아니야

최근 도전하는 문제들 중에 되게 좋은 문제라 생각돼서 소개해본다.문제: 링크(프로젝트 오일러) 다른 문제들은 어찌저찌 풀었는데, 얘는 골때린다. 도대체 해결한 사람들은 어떻게한거지 ㅋㅋ 계수의 합을 구하는 것이기 때문에 수식구하고 m=1 때려주고 a_9 곱해주면 되는건데 젠젠 모르겠다. 첫번째 접근 수학적 귀납법규칙성이 있다고 가정하고, 말도안되지만 귀납적 추론으로 아래 와 같은 공식으로 생각하여 값을 넣었다. 당연히 틀림 ㅋㅋ 두번째 접근 연립방정식 미지수 9개미지수 9개면 9개 수식이 필요하다. 즉 9개의 정답이 필요한데...1개는 이미 나와있다고 치고.. 남은 8개를 구하는데 이미 그 수가 상식을 뛰어 넘을 수 이기 때문에 아마 다른 접근 방식이 필요하다. 세번째 접근 규칙성 찾기할 수 있는대로 1..

1번 풀이 1,2,3번 7,14번 실패 알고리즘상 1~ n까지 순회하면서 lost를 순차적으로 처리하고 있기 때문에 문제 발생한 케이스일 확률이 높음. 예를 들어 Lost의 왼쪽 학생이 여분을 가졌는지 체크하는 것을 우선으로 할 경우와 오른쪽 학생이 여분을 가졌는지 우선 체크를 하는지의 차이점에 대한 테스트 케이스 필자는 위와 같이 왼쪽 학생처리 후 오른쪽 학생 처리 하는 식으로 구현을 하였기에 오름차순 Sorting 후 해결 2번 풀이 5,24번 실패 lost 학생과 reserve 학생이 겹칠 수 있다는 것. 이게 무슨 문제인가 싶지만. for(lost) 내에서 reserve 포함 현재 갯수가 1개이면 reserve 체육복을 자신이 입으면 됨. 고로 lost에서 해당 케이스는 패스된다. 끝.

1차 풀이 - std::transform을 이용한 소문자 변환 - 단계별로 적힌 그대로 처리함. - step3는 while str.find(..) { str.replace(..,.)} 으로 루프처리함 - step6은 resize(15) 적용 테스트케이스 5번 틀림 2차 풀이 - 테스트 케이스 5번 처리의 마지막 .이 남으면 제거해주라는거 추가함 제출 케이스 22,23 틀림 3차 풀이 -아래 이걸 잘못 이해함. new_id가 빈 문자열이라면, new_id에 "a"를 대입합니다. - 아래 예시 3을 보면 결과가 자릿수만큼 a로 대체되어 new_id가 단계별로 그대로 가져오는게아니라 원본을 다시 사용해야하는 경우가 존재한다고 판단했음. 예3 "=.=" "aaa" - 그게아니라 이후 스텝에 의해 3글자 이상에 ..

첫번째 풀이 약수의 갯수 구하기: O(n) 1~n까지 약수 갯수 체크 : O(n) 으로 O(n^2) 라서 시간초과 이슈 발생 총점 62/100 두번째 풀이 시간 반줄이는 방향으로 약수 갯수 구할때 범위 반쪼개서 한번에 구하는 식으로 변경 결국 O(n/2 * n )이기 때문에 역시 동일하게 시간초과 이슈 발생 총점 67/100 세번째 풀이 - 약수 갯수는 소인수분해 후 각 소수들에 대한 지수+1 의 곱인데, 이를 활용하는 방향 검토 - 소수를 저장해서 이용하는 방향으로 검토 - 소수들에 대해서 1~k 까지 m^n승 모두 찾고 약수 갯수 업데이트 하는 방향 검토 = 여기서 도저히 뭔가 방법이 떠오르지 않음. 약수 갯수 구하는데, O(루트n) 시간 걸릴 것 같은데... 네번째 풀이 - 에라토스테네스의 체 ? ..