문제 설명입출력 및 제한 사항풀이별다른 설정이 없이 굉장히 간단명료한 문제 설명이다. 하지만 풀이 과정은 간단하지 않다...요약해보자면 길이 n의 문자열 s를 {A, B, C}로만 만들 때, 오름차순 쌍의 총 개수가 정확히 k가 되도록 하는 임의의 s 하나를 출력하는 문제이다. 없다면 -1을 출력한다.* 오름차순 쌍: 인덱스 i 예를 들면 다음과 같다."ABC"라면 쌍은 (A, B), (A, C), (B, C) 로 총 3개"CBA"라면 오름차순 쌍은 0개 문제를 관찰해보자문자 하나를 왼쪽부터 차례로 붙인다고 할 때, 지금까지 만든 부분 문자열에 들어 있는 A와 B의 개수만 알면, 다음 문자를 붙일 때 쌍이 얼마나 증가하는지 결정된다.A를 붙이면 새로운 쌍 없음B를 붙이면 앞에 있던 A의 개수만큼 새로운..

문제 설명문제에 사진이 많아 글로 작성하겠습니다.루트 노드에서 순회를 시작했을 때, 처음으로 자식 노드가 2개 이상인 노드를 기가 노드라고 명칭한다. 기둥-가지를 줄여 기가 노드라 이름 붙였다.여기서 루트 노드부터 기가 노드까지의 거리와 기가 노드로부터 가장 먼 리프 노드까지의 거리를 출력하는 문제이다.입출력 및 제한 사항풀이2단계로 나누어서 풀이를 생각했다.1. 루트노드가 아닌 노드들은 기가노드 이전까지 연결되어있는 모든 노드의 개수가 2개이므로 해당 조건으로 기가노드를 찾는다.2. 기가노드로부터 DFS로 탐색하여 가장 멀리있는 노드까지의 거리를 구함.루트노드로부터 직접 DFS를 탐색해도 괜찮지만 그렇게 된다면 기가 노드로부터의 거리를 다시 계산해야하기 때문에 DFS의 출발점을 기가노드로 잡았다.내 코..

문제 설명입출력 및 제한사항풀이"소수이면서 각 자리 수의 제곱한 수를 더한 값이 1이 되는 숫자"를 찾는 문제이다.이 문제를 두 부분으로 구분하여 접근했다.1. 소수 판별2. 해당 소수가 상근수인지 판별 먼저 소수 판별은 에라토스테네스의 체를 사용하여 n이하의 소수 리스트를 찾았다. n의 범위가 100만까지 가능하니 100만까지 순회하면서 해당 수가 소수인지를 판별하는 것은 비효율적이니 에라토스테네스의 체를 사용했다.이후 해당 소수가 상근수인지 판별하는 것은 직접 시뮬레이션을 했는데, 여기에서는 중요하게 짚고 넘어가야 할 부분이 있다.100만 이하의 숫자에서 각 자리수의 제곱한 수를 더한 값의 최댓값은 999999에서 9^2 + 9^2 + ... + 9^2이다. 그럼 자리수의 제곱을 더한 값은 1 ~ 4..

문제 설명제한사항 및 입출력풀이문제가 굉장히 간단명료하다. 부연설명해보자면 수열에서 Ai 이전의 3개 숫자를 합해서 Ai를 만들 수 있다면 Ai는 좋은 수이다.(예제 똑바로 안 보고 바로 앞 3개로 풀이하다가 시간낭비한 사람...) 추가적으로 같은 값을 여러 번 써도 된다(인덱스 중복 허용) -> v+v+v, v+v+z 같은 조합도 가능. v = (x + y) + z 에서 이항하면 v - z = x + y의 형태로 나타낼 수 있기 때문에 앞의 두 수의 합을 set에 저장한다면 앞의 숫자들을 순회하며 O(n)에 판별할 수 있다. 코드를 확인해보자내 코드import sysinput = sys.stdin.readlinemis = lambda: map(int, input().split())n = int(inpu..

문제 설명피할 수 없으면 즐겨라! 파워 긍정맨입출력 및 제한사항풀이n의 크기가 매우 크다! 직관적으로 생각했을 때 각 값들은 이전 값들에 의해 결정되니 DP를 사용할 수 있을 것 같다. 하지만 10억개의 데이터를 모두 저장하기에는 512MB로 공간이 모자라기 때문에 다음과 같은 두 가지 방식을 생각했다. 1. 메모이제이션하며 재귀 (탑-다운) -> O(logn)2. 구해야하는 값들만 저장하여 해당 값들을 아래서부터 채우기 -> O(logn)모든 단계는 2개의 하위로 나누어지기 때문에 시간 복잡도는 둘 다 O(logn)이다. 직접 코드로 작성해보자! 점화식은 다음과 같다.dp[n] = ((n / 2) * (n - (n / 2))) + dp[n / 2] + dp[n - (n / 2)]-> 중앙을 쪼갠 두 값..

문제 설명제한사항 및 입출력내 풀이문제를 똑바로 안 읽고 잘못 이해해서 이상한 방향으로 풀이하다가 애먹었다... 간단히 말하자면 목표 건물을 짓기까지 최소 시간인데, 건물들은 지을 때 필요한 선행 건물이 주어지고, 선행 건물들이 모두 지어져야 해당 건물을 건설할 수 있다. (하나만 지어져도 되는 줄...) 조건들을 요약해보면 다음과 같다.건물 N개, 규칙 K개규칙: {X}를 완성해야 Y를 착수 가능각 건물의 공사 시간이 주어지고, 여러 건물을 동시에 공사할 수 있음목표 건물 W를 가장 빨리 완성하기 위한 시간관계에 사이클이 없으므로 그래프는 DAG를 성립한다. 선행 건물 관계가 이루는 DAG에서, 각 건물의 최소 완료 시간은 “선행들 중 가장 오래 걸리는 경로”를 기다린 뒤 자기 공사시간을 더한 값이다...

설명입출력 및 제한 사항풀이시간제한이 무려 5초..!이고 상품의 수는 4개까지밖에 없는 몹시 귀여운 문제이다. 주어진 값들을 순회하면서 75% 값을 찾고 있으면 정답 배열에 넣어주는 식으로 풀이했다.여기서 주의해야 할 점은 동일한 값이 여러 개 있는 경우이다.이런 입력이 있을 때 12의 4/3인 15는 하나 밖에 없으므로 정답은 9 9 12 15가 되어야한다. 사전형으로 각 숫자가 몇 개 있는지 확인하고 빼주는 방식으로 해결했다. 핵심은 다음과 같다.정상가: 4의 배수 (정상가 × 3/4 = 할인가가 정수)할인가: 3의 배수 (할인가 × 4/3 = 정상가가 정수)12의 배수(예: 300) 는 할인가도 될 수 있고 정상가도 될 수 있음. -> 역할이 모호함 정렬만 믿고 “현재 값 i에 대해 i*4 // 3..

문제 설명제한사항 및 입출력풀이문제가 굉장히 너무 간결하게 써있어서 직관적으로 이해하기 어려웠던 것 같다. S에서 시작하여 T로 이동하는데, 한 정점에서 다른 정점으로 이동할 때 목적지인 T에 더 가까워지며 이동하는 경우 이것을 합리적인 이동경로라고 한다.-> 여기서 합리적인 이동경로에 대한 정의를 다시 내려보자면 u에서 v로 이동할 때 distance(u, T) > distance(v, T) 인 경우를 말한다.이제 S에서 시작하여 T까지 도달하기까지 가능한 모든 합리적인 이동경로의 개수를 구하는 것이 문제이다. 일반적으로 주어진 격자에서 한 점에서부터 다른 점까지의 모든 최적 이동경로의 개수를 구하는 문제는 DP를 활용해서 풀이할 수 있다. DP로 풀이할 수 있는 이유는 DAG가 성립하기 때문이다.(D..