Coder's Cattitude

🔒 문제 ⌨ 입력 🖨 출력 📚 예제 📌 풀이 문제를 딱 보면 끝이 0인 애들은 뒤에 0이나 1이 올 수 있고, 끝이 1인 애들은 0밖에 못오는 것을 알 수 있다. 그래서 생각한게 0으로 끝나는 수와 1로 끝나는 수들의 개수를 따로 저장하는 것이었다. 그래서 1차원 배열이 아닌 2차원 배열로 dp를 만들어서 끝이 0인 수의 개수는 0열에, 끝이 1인 수의 개수는 1열에 저장하기로 한다. n 0으로 끝나는 수 1로 끝나는 수 1 - 1 2 10 - 3 100 101 4 1010, 1000 1001 5 10100, 100000, 10010 10101, 100001 위의 표를 개수로 나타내 보겠다 n 0으로 끝나는 수들의 개수 1로 끝나는 수들의 개수 1 0 1 2 1 0 3 1 1 4 2 1 5 3 2 .....

🔒 문제 ⌨ 입력 🖨 출력 📚 예제 📌 풀이 위의 그림을 보면 n이 1이고, 2인 경우를 제외하면 n이 3부터는 규칙이 생기는 것을 알 수 있다. 2 x n을 만들기 위해서는 2가지 방법이 있다. 2 x (n - 1) 인 경우에 1 x 2 타일 1개 붙이기 2 x (n - 2) 인 경우에 2 x 2 타일이나 2 x 1 타일 2개 붙이기 그래서 식으로 적으면 dp[n] = dp[n - 1] + dp[n - 2] * 2가 된다. 위의 그림을 보면 이해가 더 쉬울 것이다. 분홍색 형광펜으로 네모 표시를 한 부분들이 바로 이전 타일들에 추가된 부분들이다. 아래는 dp 식을 정리한 것이다. dp를 위한 배열을 만들 때, n이 아닌, n + 1 배열로 만드는 것이 편하다. 🔑 python 코드 # 2xN 타일링 2..

🔒 문제 ⌨ 입력 🖨 출력 📚 예제 📌 풀이 문제에서 주어진 숫자 S를 서로 다른 자연수들을 N개 더해서 만드는데 N의 개수의 최댓값을 구하는 것이다. 쉽게 생각하면 작은 수인 1부터 2, 3,,, 차례로 더해가면 N이 최대가 된다 는 것을 생각하면 된다. 그래서 생각해낸 풀이 방법이 등차가 1인 등차 수열을 생각해서 등차수열의 합 공식을 사용하는 것이었다. temp = 1 + 2 + 3 +,,, + n까지 더한 값은 temp = n * (n + 1) / 2 로 구할 수 있다. 이 temp 값이 S값 커졌을 때의 n 값에서 1을 뺀 것이 바로 답이다. 1을 빼주는 이유는 200을 예를 들어서 설명하겠다 200에 가장 가까운 200보다 큰 temp 값은 n이 20인 210이다. temp가 210일 때 n값..

🔒 문제 ⌨ 입력 🖨 출력 📍 제한 📚 예제 📌 풀이 🔑 python 코드 # Z import sys input = sys.stdin.readline N, r, c = map(int, input().split()) visit = 0 while(N > 0): N -= 1 size = 2 ** N # 1사분면 if r = size: visit += size*size c -= size # 3사분면 elif r >= size and c < size: visit += size * size * 2 r -= size # 4사분면 else: visit += size * size * 3 r -= size c -= ..

🔒 문제 ⌨ 입력 🖨 출력 📚 예제 예외 ex1) 1 131 -1 ex2) 1 1111 5 📌 풀이 문제를 찬찬히 보면 A -> B를 만든다기보다는 B -> A를 만드는 것이 쉽다. 그래서 규칙을 찾아보면, [규칙] B의 일의 자리 수가 1이면, B에 B를 10으로 나눈 몫을 저장한다. B를 2로 나누었을 때 나머지가 0이면, B에 B를 2로 나눈 몫을 저장한다. 3. B를 2로 나누었을 때 나머지가 0이 아니면, ans에 -1을 저장하고 ans를 출력한다. while문을 탈출하는 방법은 3개이다. 3번 조건을 생각안해서 틀렸었다 [while문 탈출] A와 B가 같아졌을 때 B가 A보다 작아졌을 때 A로 B를 만들 수 없을 때 2번, 3번은 답이 -1이다. 🔑 python 코드 # A -> B impor..

📌 풀이 문제 자체는 어렵지 않았지만, 좌표를 행렬에 대입해서 생각할 때 오류를 조금 범했다. 가로의 길이가 M이고 세로의 길이가 N인 직사각형의 경우 좌표가 (x,y)라면, 행렬의 경우 matrix[y][x]와 같다. 좌표를 행렬에 대입해서 생각하면, x좌표는 열, y좌표는 행이 되는 것이다. 그래서 아래 그림처럼 N행 M열인 행렬 (가로 M 세로 N인 행렬)을 transpose 시켜서, M행 N열인 행렬로 바꿔서 풀었다. 이렇게 행렬을 바꿔놓으면 별 문제 없이 코드가 작동하는 것을 알 수 있다. 🔑 python 코드 # 유기농 배추 import sys from collections import deque input = sys.stdin.readline T = int(input()) def bfs(x,..

📌 풀이 이 문제는 어디서부터 시작해야하는 지 나와있지 않기 때문에, NxN을 모두 다 돌 수 있도록 BFS로 풀었다. DFS로 풀어도 풀리지만 BFS로 푼 문제가 몇 개 없어서 그냥 BFS로 풀어봤다. 시간이 나면 DFS로도 풀어봐야겠다. 그래프에서 상하좌우로 이동할건데, 0행, N-1행, 0열, N-1열만 다르게 조건을 주기 싫어서 padding을 넣었다. 그래서 NxN가 아니라 (N+2)x(N+2) 그래프리고 패딩값들은 모두 0으로 채워넣었다. 문제에서 주어지는 값들을 graph에 저장하고, 만약 1이라면 BFS를 실시하고, 아니면 그냥 넘어가도록 했다. bfs에서도, 현재 위치에서 갈 수 있는 좌표들을 queue에 넣어놓고, queue가 다 빌 때까지 탐색을 진행하여 단지에 속하는 집의 수를 re..

🔒 문제 ⌨ 입력 🖨 출력 📚 예제 📌 풀이 문제를 너무 어렵게 생각했던 것 같다. 그냥 진짜 그래프 문제였다. 신기하게 풀어본다고 이것저것 시도하다 그냥 DFS로 풀었다. 문제에서 주어지는 간선들을 graph에 저장하고, DFS로 1부터 시작해서 재귀함수를 써가며 풀었다. parents = [0, 0, 0, 0, 0, 0, 0, 0] graph에 저장된 것들을 적어본다면 graph[1] = [6, 4] graph[2] = [4] graph[3] = [6, 5] graph[4] = [1, 2, 7] graph[5] = [3] graph[6] = [1,3] graph[7] = [4] 이다. dfs(1)을 해주면 graph[1]에서 첫번째 값인 6의 parents가 0인지 확인하고, parents[6]을 1..

🔒 문제 ⌨ 입력 🖨 출력 📍 제한 📚 예제 📌 풀이 이 문제는 union-find의 기본 문제가 아닐까 싶다. 그냥 보자마자 어,, union-find다 라는 생각이 들었다. 문제를 푸는 것 자체는 안어려웠지만, error가 많이 나서 보니까 1. Recursive error 이 오류는 Python이 정한 최대 재귀 깊이보다 재귀의 깊이가 더 깊어져서 발생한다. sys.setrecursionlimit(10**6) 을 사용해서 Python이 정한 최대 재귀 깊이를 변경해서 풀어준다. 2. memory 초과 이건 pypy로 했더니 발생했다. 해결법은 딱히 찾지 못했다. 3. 시간초과 root 함수를 짤 때 처음엔 root를 찾기만 했지, 찾으면서 root값들을 변경해주는 것이 없었다. 그래서 root를 찾..

🔒 문제 ⌨ 입력 🖨 출력 📚 예제 📌 풀이 1. 책의 위치를 받은 배열을 음의 정수(minus_loca)와 양의 정수(plus_loca) 두 개의 배열로 나눈다. 2. 음의 정수들을 배열에 넣을 때, 계산하기 편하게 -1을 곱해서 넣는다. 3. -1을 곱한 음의 정수와 양의 정수를 내림차순으로 배열에 넣는다. => 가장 큰 보폭인 애들끼리 묶어서 최대한 많은 양을 옮기기 위해 4. 음의 정수와 양의 정수 각각을 M칸씩 건너 뛰면서 새로운 배열(minus_step, plus_step)에 저장한다. => 최대로 들 수 있는 책의 개수만큼 옮길 책들의 묶음을 나눠줌 5. steps를 계산해준다. 5-1. minus_step의 인수 수가 0 인 경우, plus_step의 가장 큰 값은 steps에 한번만 더해..