Dalin's Archive

문제 보러 가기! 얼마 전에 누적합을 처음 공부하고, 관련된 문제를 풀고 싶어서 스터디 문제에 추가했다.(한 사람 당 한 문제씩 추가하는 방식으로 스터디를 하는 중입니다~) 그런데 단순한 누적합..만으로는 해결할 수 없었다..ㅠㅠ 0 ≤ 모기의 입장 시각 < 모기의 퇴장 시각 ≤ 2,100,000,000... 너무 컸기 때문이다. 그래서 계속 시간 초과, 메모리 초과..와 싸우다가 스터디를 할 때까지 못 풀었다. 스터디원 분께서 설명해주셔서 값, 좌표 압축이라는 아이디어를 처음 알게 되었다! 그 아이디어를 적용하고, 다른 부분도(이것도 아래에서 설명하겠다.) 바꾸니까 문제를 풀 수 있었다 ! 전에 코드(시간 초과) 💥 import collections import sys input = sys.stdin...

문제 보러 가기!! 와아... 많은 시간 초과를 겪은 끝에 드디어 맞았다. 🤣🤣 아이디어 ⭐ N이 K로 나눠지는지 본다. -> N을 두 번 써서 K로 나눠지는지 본다. -> 쭉 본다. K로 나눠지면(나머지가 0이면) 그만두고, N을 몇 번 썼는지 출력한다. 불가능한지 판단하는 기준은 ?? 나머지를 쭉 저장한다. -> 나왔던 나머지가 또 나오면, 그 패턴이 반복된다는 거니까 불가능하다고 본다. (이걸 증명하는 수학적인 개념은 모르겠는데, 찾아봐야겠다.) N을 n번 쓸 때 모듈러 연산을 활용했다 !! 나도 처음 알게 된 것이라서, 기억할 겸 쓴다. 모듈러 연산의 모듈러는 modulo 즉 나머지이다. 나머지를 구할 때 사용할 수 있는 세 가지 성질이 있다. (A+B) % C = (A%C + B%C) % C (..

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

문제 보러 가기! 접근 💚 처음에는 소수가 나와서 어떻게 접근할지 고민했다. 우주 생명체 수 N에서 핑거 스냅으로 할 수 있는 4가지 일을 하고, 그게 A와 B 사이의 소수인지 매번 확인하는 것은 힘들 것 같았다. (매번 소수인지 쭉 계산을 해야 하니까.) 그래서 좀 생각을 바꿔봤다! A, B는 100000 이하니까 10만 이하의 소수를 모~두 구하는 것이다. (에라토스테네스의 체로 구했다.) 그리고 A 이상 B 이하의 소수들을 리스트에 저장해두고, 핑거 스냅으로 4가지 일을 한 후에 그 우주 생명체 수가 그 리스트의 값들 중에 있는지 보는 것이다. 최소 몇 번의 핑거 스냅을 해야 할지 구하는 것! 즉 최단 거리를 구하는 것과 같으니까 BFS로 풀었다. 4가지 일을 한 후의 우주 생명체 수를 보고 범위 ..

문제 보러 가기(로그인해야 볼 수 있어용) ㅠㅠㅠㅠㅠㅠ 3~4시간 힘겨운 시간을 보내고 ㅠㅠㅠ 드디어 맞았다 ㅠㅠㅠㅠㅠ 이렇게 오래 씨름한 문제는 오랜만이다... 접근은 그렇게 어렵지는 않았고, 1시간 만에 파이참에서는 정답이 나오게 코드를 짤 수 있었다. 그런데 문제 채점 사이트에서 런타임 에러 나와서 해결하느라고 정말 정말 힘들었다 ..!! 맨 처음 짠 코드 👩‍💻 import sys sys.stdin = open('1242_input.txt') T = int(input()) hex_change = { '0': '0000', '1': '0001', '2': '0010', '3': '0011', '4': '0100', '5': '0101', '6': '0110', '7': '0111', '8': '10..

문제 보러 가기! 간단 문제 소개 ✅ 정수 s가 주어지는데, 이걸 t로 바꾸는 최소 연산 횟수를 구하는데, 가능한 방법을 출력해야 한다. s+s, s-s, s/s, s*s 연산을 사용할 수 있다. 바꿀 수 없는 경우도 존재한다. 아이디어 😄 최소 연산 횟수를 구하는 것이고, 가능한 방법이 여러 가지일 때 사전 순으로 앞서는 것을 먼저 출력해야 한다. => BFS 로 풀어야겠다고 생각했다. 그리고 s + s 는 2*s이고, s-s는 0이고, s*s는 s**2이고, s/s는 1이다. 이걸 좀 더 보다 보니까 -는 고려할 필요가 없다.라는 것을 알 수 있었다. 빼기하면 0이 되는데, t는 0보다 크다. 0이 되면 나누기는 불가능하고 더하기, 곱하기, 빼기해도 0이 된다. 그러니까 빼기를 해서는 전혀 답이 될 ..