나만의 개발블로그

풀이 초기 생각한 방법은 아래 두 번째 코드처럼 각 위치에서 슬라이싱한 값 까지의 합 중 가장 큰 값을 출력하고자 했지만 2% 에서 시간 초과 발생 그래서 dp를 활용한 문제 해결을 위해 현재 위치 전까지의 가장 큰 값(이전 dp값) + 현재 위치의 배열 값과 현재 배열의 값 중 큰 값을 현재 dp의 값에 저장하여 최종적으로 가장 큰 값을 출력하여 해결! 정답 코드 import sys input = sys.stdin.readline n = int(input()) li = list(map(int,input().rstrip('\n').split())) dp = [0]*n dp[0] = li[0] for i in range(1,n): dp[i] = max(dp[i-1]+li[i], li[i]) print(ma..

풀이 처음엔 단순히 같은 값으로 예를 들어 'EE', 'WW'의 경우 카운팅을 해주는 형식으로 했지만 어림도 없었고 이후 'EW'의 경우 카운팅을 해주고자 하니 'WE'의 경우엔 서로 다른 방향으로 가니 컨트롤 하기가 어려워서 고민하다가 그냥 반복문을 돌리면서 visit로 방문 체크를 하며 확인해볼까 해서 풀어보니 해결! import sys from collections import deque input = sys.stdin.readline n = int(input()) li = list(input().rstrip('\n')) visit = [0]*n result = 0 for i in range(n): if not visit[i]: q = deque([i]) visit[i] = 1 while q: s ..

풀이 해당 문제는 백트래킹 문제로 이전에 포스팅한 집합과 순열을 사용하면서 itertools에 있는 메서드를 가지고 온거에 대한 찝찝함으로 백트래킹 문제를 하나 풀고 싶었다..핳 무튼 해당 문제는 단순히 cnt와 x를 1씩 증가 시키는 형식으로 하여 cnt가 m이 될 경우 출력하며, x는 범위를 지정해주는 역할로 사용 그리고 li에 추가한 뒤 함수 실행 이후 return 되는 경우엔 다시 가장 최근 값을 pop 함수로 빼내는 형식으로 백트래킹 문제를 해결 def NM(cnt,x): global n,m if cnt == m: print(*li) return for i in range(x,n+1): li.append(i) NM(cnt+1,i+1) li.pop() return import sys input =..

풀이 처음엔 조합을 활용해서 풀면 되나 싶었지만 예제 1번의 출력 값을 확인 후 조합의 값으로는 6이 나오는데 7이 어떻게 나올 수 있을까 확인하다가 아래로 조금 더 스크롤 해보니 7이 되는 경우를 알려줘서 순열로 푸는 것을 확인할 수 있었다. 그리고 이번 문제는 k 개의 수끼리 순서대로 나열한 값의 중복되지 않는 개수를 출력하는 것이기에 숫자가 아닌 문자로 초기 셋팅을 해줘 더 편하게 해결. from itertools import permutations n,k = int(input()),int(input()) li = [str(input()) for _ in range(n)] result = set() for i in list(permutations(li, k)): val = '' for j in i:..

풀이 델타 탐색 중 아래와 오른쪽으로만 탐색하도록 하며, mtx의 di, dy의 값에 현재 위치 값을 더한 값이 범위 내에 있는지 확인 이후 가장 아래의 가장 오른쪽인 도착 지점에 위치했을 경우 flag를 True로 변경 후 q에 남아있어도 while문 탈출하도록 하기 또한 visit를 활용해서 같은 위치를 재방문하지 않도록 해서 해결 import sys from collections import deque input = sys.stdin.readline n = int(input()) mtx = [list(map(int,input().rstrip('\n').split())) for _ in range(n)] visit = [[0]*n for _ in range(n)] visit[0][0] = 1 q = ..

풀이 왕복으로 범위가 지정되는 것이기에 아래와 같이 구현하여 풀이 실수해서 오답 제출한 부분으로는 print(i%n+1) 으로 해야하는데 print(i%5+1)로 제출했다는 점... 초기 예제 값 조심하기!! import sys input = sys.stdin.readline n,k = map(int,input().split()) li = list(map(int,input().rstrip('\n').split())) ch = li + li[::-1] rg = 0 for i in range(len(ch)): if rg

풀이 첫 입력값과 이후의 입력 값을 대조한 뒤 다를 경우 물음표(?) 로 변경 후 최종적으로 출력해서 풀이 import sys input = sys.stdin.readline li = [] for i in range(int(input())): if i == 0: li = list(input().rstrip('\n')) else: ch = list(input().rstrip('\n')) for j in range(len(li)): if li[j] != ch[j] and li[j] != '?': li[j] = '?' [print(i,end='') for i in li]

풀이 pypy로 제출해서 겨우겨우 시간을 맞춘듯한 코드... 진짜 꾸역꾸역 올라가는거 보고 숨 참고 지켜보느라 힘들었다... 우선 보기에서 나온 것처럼 각 구역별 테두리가 있을 텐데 해당 테두리끼리 회전 수에 맞게 회전을 한 결과를 출력하면 된다. 그래서 주어진 n과 m 중 작은 수의 값에 2를 나눈 몫으로 테두리의 개수를 체크 이후 i,i 로부터 테두리를 한 바퀴 쭉 돌아다니면서 tmp 값을 현재 arr에 담아주고 현재 arr 값을 tmp에 담아주어 교체하는 식으로 해결 탐색을 하기 위한 조건 분기는 아래의 주석으로 체크 import sys input = sys.stdin.readline n,m,c = map(int,input().split()) arr = [list(map(int,input().rst..

풀이 n 부터 0까지 반복문을 활용해 조사하면서 i+자릿수의 합을 한 결과가 n과 같을 경우 result에 할당 문제에서 가장 작은 분해합을 찾기에 새롭게 result를 갱신 그리고 만약 그대로 result가 0의 경우 그대로 0을 출력하여 해결 n = int(input()) result = 0 for i in range(n-1,0,-1): if n == i+sum(list(map(int,str(i)))): result = i if result: print(result) else: print(0)

풀이 deque를 활용한 BFS 방식의 풀이 ( 더 빠름 ) q에는 초기값으로 n과 0으로 값과 그에 따른 카운팅을 넣어주기 이후 3,2로 나누어 떨어지는 경우와 -1한 경우를 q에 추가하기만 해서 1이 되는 경우 제출을 했지만 시간초과가 발생하기에 가지치기를 해서 나누어 떨어질 경우 li에 cnt 값을 넣어주어 만약 중간에 q를 통해 접근했던 적이 있다면 더 이상 반복해서 조회하지 않도록 해서 풀이 DP를 활용한 풀이 li의 1,2,3 번 배열에 초기값을 채운 다음 3,2로 나누어 떨어지는 경우와 -1한 경우를 조사해서 해당 값의 li의 index 값에 +1 을 하는 방식 여기서 중요한 점으로 3과 2가 함께 나누어 떨어지는 경우가 있기에 조건 분기를 가장 처음에 해줘서 풀이! BFS 풀이 from c..