본문 바로가기
728x90

전체 글423

[python] 백준 17626 Four Squares https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 문제 해결 n보다 작은 수의 제곱수의 개수를 연결하는 것이므로 dp를 이용하는 것이 좋겠다는 생각을 하게 된다. 시간제한이 0.5초이기 때문에 빡세다. (python3로는 계속 탈락... pypy3로 풀었는데 python3까지 최적화를 못시키겠다.) 1 = $1^{2}$ 이므로 dp[1] = 1 dp[0] = 0으로 고정한다. 2부터는 for문을 통해 알아갈 것.. 2023. 3. 14.
[python] 백준 1700 멀티탭 스케줄링 https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 문제 해결 순서대로 멀티탭을 꽂고 빼고 해야한다. 뒤에 같은 종류가 있으면 안빼고 바로 연결하면 된다. 혹은 멀티탭에 비어있는 것이 있으면 꽂으면 된다. 만약 현재 연결해야 하는 것이 있고 멀티탭에 연결되어 있는 물건 중 같은 종류가 없으면 한 종류의 물건을 빼야한다. 빼야 하는 것은 뒤에 물건들을 보고 연결할 필요가 없거나 가장 늦게 연결할 필요가 있는 것을 제거하는 것이 낫다. CODE fro.. 2023. 3. 14.
[python] 백준 1783 병든 나이트 https://www.acmicpc.net/problem/1783 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 해결 bfs로 풀면 끝이라고 생각했지만 시간초과가 났다. bfs, dfs로 시간초과가 나면 결국 dp를 이용해야한다고 생각했다. 어느 방향으로 움직이던 오른쪽으로 이동을 해야한다. 열이나 행이 1칸이면 무조건 움직일 수 없기 때문에 답은 1 행이 두칸이면 열을 2칸 움직여야하기 때문에 열이 최소 3열 이상 있어야 움직인다. 4번 이상 움직이려면 움직일 수 있는 방법으로 한번씩 움직여야 한다. (-2,1),(2,1),(1,2),(-1,2) =>total (0.. 2023. 3. 14.
[python] 백준 1343 폴리오미노 https://www.acmicpc.net/problem/1343 1343번: 폴리오미노 첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다. www.acmicpc.net 문제 해결 X가 연속 4번 나올 수 있으면 'AAAA'로 교체한다. X가 연속 2번 나오고 '.'이 나오거나 끝나게 되면 'BB'로 교체한다. X가 연속으로 홀수번 나오면 교체 불가능으로 -1 출력 CODE import sys input = sys.stdin.readline board = list(input().rstrip()) ans = [] cnt = 0 for i in range(len(board)): if board[i] == 'X': cnt += 1 if cnt == 4: for _ in r.. 2023. 3. 14.
728x90