Dalin's Archive

문제로 가기 행의 번호와 열의 번호를 각각 등차수열로 봐주면서, 그 칸의 숫자를 이어 붙인다. 그랬을 때 만들 수 있는 정수 중 가장 큰 완전 제곱수!를 구하는 문제였다. 나는 기억이 안나는 수학적 개념이 하나 있어서 쓴다..ㅎㅎ 등차 수열: 연속하는 두 항의 차이가 일정한 수열 위키백과 (이미지 출처- 위키백과) 이러한 식이 나온다. 여기에서 d(두 항의 차이)를 '공차'라고 부른다. 예) 1-3-5-7-9 (2씩 차이), 4-10-16-24-30 (6씩 차이), 1-1-1-1-1 (0씩 차이), 100-99-98-97-96(-1씩 차이) 설명 🗝 a1 즉 첫째 항과 d, 즉 공차를 상황에 따라서 다 봐줬다. N, M이 9보다 작으니 브루트포스하게 쭉~ 봐줘도 되겠다고 생각했다. 그래서 4중 for문이..

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

문제 보러 가기 정말 브루트포스하게 풀었다. 하나 하나 따지면서!! 도시 정보를 다 보면서 치킨집 위치 찾기. 찾는 김에 개수도 세기 치킨집이 M개보다 크면, 치킨집 중 M개 뽑기(순서 상관 없으니 조합) - 치킨집이 M개 이하이면, 따로 뽑을 필요 없음. 각각의 경우를 보면서, 도시의 치킨 거리 계산하기. (도시 정보를 쭉 보면서 집을 만나면, 집마다 '치킨 거리' 찾기. 집마다 치킨 거리 찾을 때는, 그 경우에 남겨두기로 한 치킨집들을 다 돌아보면서 젤 가까운 거리를 찾음.) 가장 도시의 치킨 거리 작을 때가 정답! import sys input = sys.stdin.readline MIIS = lambda: map(int, input().split()) N, M = MIIS() cit..

문제 보러 가기 N개 정수로 이뤄진 수열이 있다. 크기가 양수인 부분 수열(원소가 1개 이상인 부분 수열이라는 뜻 같다) 중에서 원소들을 다 더한 값이 S가 되는 경우의 수 구하기!! dfs에서 몇번째 인덱스를 볼건지(depth), 그때까지 부분 수열에 포함한 원소의 인덱스들(history), 그때까지 부분 수열 원소들의 합(total)을 가지고 다녔다. 크기가 양수이고(=history가 빈 문자열이 아니고), 그 수열 원소를 다 더한 값이 S면 그때까지의 history(몇 번 몇 번 인덱스를 포함했는지)를 set에 넣어줬다. depth번째 수를 포함하는 부분 수열을 만드는 경우, 포함하지 않는 부분 수열을 만드는 경우를 따져주었다. 처음에는 런타임에러(RecursionError)가 떴다..ㅠㅠ N이 최..

문제 보러 가기~~ 아이디어 🤩 몇 자리 숫자가 들어오는지에 따라서 다른 행동을 하라고 했다. 그래서 숫자(단, str 형식으로 입력받음)와 그때까지 더한 홀수의 합을 받아서, 특정한 행동을 하는 함수를 만들었다. 몇 자리인지에 따라서 다른 행동을 하고, 한 자리가 되어서 종료될 때까지 재귀로 계속 돌린다. 한 자리 -> 그때까지의 홀수의 개수를 리스트에 추가하고 리턴! (나중에 최대 홀수의 개수, 최소 홀수의 개수를 출력한다.) 두 자리 -> 그 수를 두 개로 나눠서 합을 구해서 새로운 수로 생각한다. (12면 1과 2로 나눈다. -> 1+2를 해서 3을 새로운 수로 생각하기) => 새로운 수, 그때까지 홀수의 합 + 이 새로운 수에 들어간 홀수의 개수를 인자로 주어서, 또 함수에 넣는다. 세 자리 이..

문제 보러 가기! 아이디어 💕 도시 간 이동하는 데 드는 비용이 행렬에 저장되어 있다. 모든 도시를 순회하고, 다시 원래 출발점으로 돌아와야 한다. 이때 가장 적은 비용이 들 때 얼마나 드는지 출력하는 문제이다. 도시가 최대 10개니까 브루트포스하게 다 봐도 될 거 같다고 생각했다. 일단은 모든 도시에서 출발해보았다. 방문했던 곳은 못 가니까 방문 체크도 하고 ! 다만 원래 출발점으로는 다시 돌아와야 하니까 그 부분은 다르게 처리했다. 처음 코드(파이썬-시간초과, 파이파이- 3140ms) 😂 import sys input = sys.stdin.readline N = int(input()) cost_matrix = list(list(map(int, input().split())) for _ in range..