문제해결5 백준 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. Codeforces Round 946 (Div. 3) 간만에 Div.3를 쳤는데 첫 민트 퍼포먼스가 떠서 글을 작성해본다. 민트 퍼포먼스가 뜬거지 민트가 된건 아니다... Div 3, 4만 열심히 치다보면 블루에 가는 날이 올 수도?? 무슨 문제가 나왔는지 살펴보자. A. https://codeforces.com/contest/1974/problem/A Problem - A - Codeforces codeforces.com5x3 화면 안에 1x1과 2x2 크기의 앱들을 넣으려면 몇 개의 화면이 필요한지 묻는 문제다.브르투포스로 카운트 했다. A번 답게 쉬운 문제 정답 코드 : https://codeforces.com/contest/1974/submission/261799934 B. https://codeforces.com/contest/1974/proble.. 2024. 5. 21. 백준 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. Codeforces Round 918 (Div. 4) 간만에 열리는 Div.4턱걸이 그린이라 강등 될까봐 부계정으로 쳤다.아마 Div.4 올솔 할 수 있는 실력이 될 때까지는 부계로 칠듯하다.블루까지는 찍어보고 싶다. D번까지는 쉽게 풀었는데 E번부터 막혔다. E번까지는 풀어야 그린 퍼포가 나오는데..E번은 누적합으로 어떻게 하면 되지 않을까 삽질하다가 못풀었고F번은 a_i b_j인 (i, j) 순서쌍 개수 구하는 문제인데 inversion counting을 사용하면 되는걸 생각하지 못했다.G번은 읽어보지도 않았다.그래도 간만에 코드포스를 하니 재밌었다. 콘테스트가 끝나고 E, F번은 다시 풀어보며 업솔빙을 했고 G번은 다익스트라 문제라는데 풀고 싶을 때 풀어봐야겠다.(라고 하면 대게 안푼다) https://codeforces.com/contest/191.. 2023. 12. 29. 백준 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 다음
