Dalin's Archive

문제 보러 가기! 문제 2행 n열에 한 칸마다 스티커가 있다. 각각에는 점수가 있다. 한 스티커를 쓰면, 그것과 변을 공유하는(상하좌우) 스티커를 못 쓴다. 쓸 수 있는 스터커 점수의 최댓값을 구하는 문제였다. 풀이 DP로 풀었다. dp 테이블을 2Xn 리스트로 만들었다. 그 위치의 스티커를 뗐을 때, 그때까지의 최대 점수를 저장한다. 1행 n열의 스티커 뗐을 때의 최대 점수 = (2행 n-1열 스티커 뗐을 때의 최대 점수 or 2행 n-2열 스티커 뗐을 때의 최대 점수) + 1행 n열 스티커 점수이다. 2행 n열의 스티커 뗐을 때의 최대 점수는 위의 식에서 2행을 1행으로, 1행을 2행으로만 바꾸면 된다! n이 1일 때, 2일 때는 따로 수작업으로 처리했다. 하늘색 숫자는 그 자리의 스티커 떼면 얻는 ..

문제 보러 가기! 문제 1n의 수로 이뤄진 수열이 주어진다. 1n까지 수를 순서대로 스택에 넣었다 뺐다 하면서 주어진 수열을 만드는 방법을 출력해야 한다. 풀이 처음에는 막막했는데, 스택의 성질을 생각하면서 구현했더니 됐다 ! 스택 - Last in First out!! import sys input = sys.stdin.readline MIIS = lambda: map(int, input().split()) n = int(input()) arr = list(int(input()) for _ in range(n)) # 입력된 수얼 ans = [] stack = [] idx = 0 # 입력된 수열 어디까지 만들었는지 for i in range(1, n+1): stack.append(i) # 스택에 넣는다 ..

문제 보러 가기! 평범한 BFS 문제에서 조금 더 생각해야 했다.. dq에는 위치, 얼마나 걸렸는지를 가지고 있는다. 앞으로 걷고, 뒤로 걷고, 순간이동하는 경우를 범위, 방문 체크한 후에 dq에 넣는다. 일단 N이 0일 때는 곱하기 2해도 0이고, -1은 해도 점점 멀어지는 거니까 괜히 시간만 든다. N이 0일 때는 일단 무조건 한 칸 앞으로 가야 하니까, dq에 (N+1, 1)을 넣고 시작한다. 틀리다가 질문 게시판의 반례!!를 보고 문제를 알았다. dq에 넣을 때 방문 체크를 하면 안되고, 뺄 때 방문 체크를 해야 한다! 1 10의 경우에 1->2->4->5->10으로 가는 게 젤 빨리 가는 것인데, 1에서 2로 갈 때 걸어서 갈 수도, 순간 이동해서 갈 수도 있다. dq에 넣을 때 방문 체크를 하..

문제 보러 가기! 오.. 문제가 생각보다 쉽게? 직관적으로? 풀려서 신기하다... 문자열이 주어졌을 때, 회문이 아닌 가장 긴 부분 문자열의 길이를 구하는 문제이다! 그런 부분 문자열이 없으면 -1을 출력하라고 했다. 일단 -1을 출력해야 하는 경우를 생각해봤다. 단어가 한 글자인 경우(어떻게 봐도 회문이 되니까!), 맨 처음에 쭉~ 봐서 모두 같은 알파벳으로 이뤄진 경우에는 -1를 출력하고 끝냈다. 그게 아닌 경우는 bfs처럼 봤다. 일단 전체 문자열을 넣어주고 시작한다. popleft한 것이 회문인지 본다. 회문이 아니면, 그 문자열 길이를 리턴한다. 그게 젤 긴 문자열일테니까 정답! 회문이라면 그 문자열에서 맨 앞 한글자를 뺀 단어, 맨 뒤 한글자를 뺀 단어를 큐에 넣는다. -이걸 한 글자가 될 때..

문제 보러 가기! import sys input = sys.stdin.readline MIISS = lambda: map(int, input().strip().split()) dp = [[0] * 100_001 for _ in range(4)] dp[1][1] = 1 dp[2][2] = 1 dp[1][3], dp[2][3], dp[3][3] = 1, 1, 1 for i in range(4, 100_001): dp[1][i] = (dp[2][i - 1] + dp[3][i - 1]) % 1_000_000_009 dp[2][i] = (dp[1][i - 2] + dp[3][i - 2]) % 1_000_000_009 dp[3][i] = (dp[1][i - 3] + dp[2][i - 3]) % 1_000_000_0..

문제 보러 가기! 하늘색 숫자는 원래 그 자리의 숫자이다.(arr에 저장했다.) dp는 n X n 2차원 리스트로 만들었다. 세로는 위에서부터 몇 층 내려왔는지, 가로는 지금의 가로 위치를 뜻한다. 그 위치로 올 수 있는 숫자 중 큰 수(각 층에서 0번째 자리는 바로 위에서만 내려올 수만 있고, 가장 오른쪽 수는 대각선 왼쪽에서만 내려올 수 있다. 다른 수들은 바로 위 or 대각선 왼쪽 수 중 큰 수!! )에다가 원래 그 자리의 숫자를 더해서 저장했다. 아! 문제에 '아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.'라고 쓰여 있는데, 인덱스로 따지면..! 아래 그림처럼 된다. 노란 동그라미 친 숫자 기준으로 보면, 왼쪽 대각..

문제 보러 가기! 처음에 아이디어가 딱 떠올랐다 ! 그 후에 문제를 잘 이해하지 못해서, 조건 생각 못해서 틀리다가 맞았다 !! 정답률이 낮은 이유를 알 것 같다.. 꼼꼼하게 문제를 읽어야 겠다..!! 사전에 있는 단어가 들어온다. 그 후에 문장이 들어온다. 그 문장을 해석하는 경우의 수를 출력하는 문제이다! 그 문장의 단어들이 사전에 있는 단어와 첫 글자와 끝 글자가 일치하고, 가운데 글자들이 있으면 해석될 수 있다. 예를 들어서 사전에 abc, cba가 있는데, 'acb'가 들어오면 두 가지 방식으로 해석될 수 있는 것이다. 그래서 2차원 리스트, defaultdict을 이용해서, 어떤 단어가 들어왔을 때 몇 가지 방식으로 해석될 수 있는지 개수를 저장했다. 2차원 리스트를 53X 53로 만들었다. ..

문제 보러 가기! 문제와 함께 하는 즐거운 크리스마스 이브 ~ 구해야 하는 것은 두 기어가 주어졌을 때 맞물리게 하는 가장 짧은 가로 너비이다. 즉 맞물리는 최대 길이를 찾으면 된다. (두 기어의 길이 합에서 맞물리는 최대 길이를 빼면 정답이 된다.) part1, part2에 오는 문자들의 개수가 적어서, 일일이 다 봐주었다! 두 기어가 맞물리는지, 아닌지 봐줄 때 아래 세 가지 경우를 봐줄 수 있다. 1번, 2번 경우이다. 노란색 왼쪽이 1번, 오른쪽이 2번 경우이다. 1번) 짧은 기어를 기준으로, 짧은 기어가 긴 기어 왼쪽에서 하나씩 더 겹쳐지면서, 그럴 때 맞물리는지 볼 수 있다. 2번) 짧은 기어가 긴 기어 오른쪽에서 하나씩 더 겹치지면서, 그럴 때 맞물리는지 볼 수 있다. -> 맞물리면 그때까지..

문제로 가기! 몇 초에 몇 번 이동했을 때, 그때까지 먹은 자두 수를 dp 테이블에 저장했다.(2차원 리스트로 dp) 이 부분에 점화식 설명을 적을 것이다.. 그림으로 그려서 설명하려고 하는데, 지금 태블릿을 누구한테 빌려줘서... 내일 할게용 초가 지나갈 수록 자두가 몇번 나무에서 떨어지는지 쭉~ 보면서, 몇 번 나무에서 떨어졌는지에 따라서 다르게 했다. 1번 나무에서 자두 떨어졌을 때) 한 번도 이동 안했을 때 1번 나무에서 시작하니까, dp[0][j]가 전에 비해서 1 증가. 그 것보다 많이 이동했을 때는, 짝수번 이동했는지 홀수번 이동했는지에 따라서 몇 번 나무에 있는지 알 수 있다. 짝수번째로 이동했으면 1번 나무에 있는 것이다. 최대 이동 횟수일 때는 따로 처리한다. 2번 나무에서 자두 떨어졌..

문제 풀러 가기! 정성스럽게 구현했다 ^^ 엄청난 알고리즘!!보다는, 조건을 잘 따지고 실수하지 않으면 되는 것 같다.. 잘못을 찾을 때, 디버깅 연습도 해서 좋았다. ^^ 내가 실수했던 부분들!✅ 가을) 나무 개수가 5의 배수이면 인접한 8개 칸에 나이가 1인 나무가 생긴다. 그런데 나는 ni, nj = i+ki, j+kj 부분을 처음에 안 썼다.. 그리고 ni, nj가 아니라 ki, kj를 범위 체크하고, ki, kj부분에 나무를 더해줘서 문제였다... K년 후에 남은 나무 개수를 셀 때! 처음에는 쭉 보면서 그 지점에 나무가 있으면 1을 더했다. 그런데 그 지점에 나무가 여러 그루 있을 수도 있으니까, ground_tree[i][j]의 len을 세줘야 했다. 코드 👩‍💻 import sys inpu..