문제해결/백준3 백준 11112번 (C++) https://www.acmicpc.net/problem/11112 1525번이랑 비슷한 문제다. 다른 점이 있다면 1525번은 입력이 한 번만 들어오는 반면에 11112번은 입력이 100개까지 들어올 수 있다는 점이다. 그래서 1525번 풀듯이 매 입력마다 최단거리를 구하면 당연히 시간초과가 난다. 해결 방법은 123 456 78# 에서 시작해서 모든 상태의 거리를 미리 구해놓고(전처리) 한 상태를 입력 받으면 바로 정답을 출력하는 것이다. 모든 경우의 수 9! 에 나올 수 없는 경우(inversion)을 제거하면 9! / 2 = 181,440 번만큼만 탐색하면 된다. 코드 : #include #include #include #include #include #include #include #incl.. 2024. 9. 20. 백준 29730번 (C++) https://www.acmicpc.net/problem/29730 29730번: 임스의 데일리 인증 스터디 취업 준비생 임스는 취업 준비를 하면서 그날그날 무슨 공부를 하였는지 기록하기 위해 데일리 인증이라는 스터디를 시작했다. 임스는 매일 무슨 공부를 하였는지 적으면서 몇 개의 규칙을 정 www.acmicpc.net n개의 문자열이 주어지는데 boj.kr/문제번호 로 이루어진 문자열인 경우와 아닌 경우를 나누고 아닌 경우부터 정렬 후 출력하는 문제다. 문제번호가 1이상 30000이하라 boj.kr/123456789 같은 경우는 링크가 아닌 경우로 취급해야 하는줄 알았는데 그렇게하면 문자열 최대 길이가 100이라 정수 표현 범위를 넘어간다. 그래서인지 문자열이 boj.kr/로 시작하는 경우는 링크, 반.. 2024. 1. 7. 백준 30446번 (C++) https://www.acmicpc.net/problem/30446 30446번: 회문수 어떤 양의 정수 $P$에 대해 $P$를 구성하는 숫자들을 왼쪽부터 적는 경우와 오른쪽부터 적은 결과가 서로 일치할 경우, $P$를 회문수(palindrome number)라 한다. 예를 들어 $1$, $101$, $12322321$은 모두 회문 www.acmicpc.net ICPC 2023 예선에 나온 문제다. 당시에 G번을 붙잡고 있다가 이분탐색으로 풀 수 있겠다 싶었지만 최적화가 부족해 시간초과가 났고 30분 남은 상황에서 이 문제를 쳐다봤다. 하지만 멘탈이 나간 상황이라 풀지 못했다. 지금 다시 풀어보니 간단한 문제였다. 10^10이하의 숫자 N이 입력되면 1부터 N까지 숫자 중에 회문수가 몇 개인지 세는 문제.. 2023. 12. 25. 이전 1 다음
