https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 나누고 빼는 대신 곱하고 더하는 것으로 바꿔 풀었다. N에서 1로 줄여나가는 것이 아니라, 1에서 N으로 늘려가는 것으로 방향을 반대로 보고 풀었다. 먼저 dp를 모두 N인 리스트로 초기화해주고, index 1의 값만 0으로 바꿔준다. 1부터 N-1까지 다음을 반복한다. 현재 i에서 3 곱한 것이 N 이하면, graph[i]+1의 값과 graph[i*3] 중 최솟값 취하기 현재 i에서 2 곱한 것이 N 이하면, graph[i]+1의 값과 graph[i*2] 중 최솟값 취하기 현재 i에서 1 더한 것이 N 이하면..

https://programmers.co.kr/learn/courses/30/lessons/87946 코딩테스트 연습 - 12주차 XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던 programmers.co.kr 시간제한 코테를 풀어보며 느낀 점... 그냥 생각 안 나면 약간 무식하게 느껴지더라도 모든 경우의 수를 고려해서 풀기 그래서 itertools의 permutations로 모든 가능한 순서를 구하고, 그에 따라 최대로 방문할 수 있는 던전의 수를 구했다. 그 중 최댓값을 반환하면 된다 더 좋은 방법이 있겠지?? from itertools import pe..

https://programmers.co.kr/learn/courses/30/lessons/87377 코딩테스트 연습 - 10주차 [[2, -1, 4], [-2, -1, 4], [0, -1, 1], [5, -8, -12], [5, 8, 12]] ["....*....", ".........", ".........", "*.......*", ".........", ".........", ".........", ".........", "*.......*"] [[0, 1, -1], [1, 0, -1], [1, 0, 1]] ["*.*"] [[1, -1, 0], [2, -1, 0], [4, - programmers.co.kr 문제에 제시된 참고사항을 참고해 두 직선의 모든 좌표가 정수인 교점을 구하는 함수 inte..

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 백트래킹으로 풀어보려고 했는데, 일단 내장 combinations 써서 풀었다 .. 1 ~ N개까지 모든 부분 수열을 구해보고 그 합이 S이면 answer 하나씩 증가해주기 import sys from itertools import combinations N,S = map(int, sys.stdin.readline().split()) nums = list(map..

https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 왼쪽으로 회전 또는 후진하기 위해 현재 방향을 key, 회전 또는 후진을 위한 이동 방향을 value로 갖는 딕셔너리를 정의한다. move_dict는 각 방향을 key로, 그 방향으로 이동하기 위한 (dx, dy)를 value로 갖는다. 이후 문제의 조건에 맞게 다음을 반복한다. 왼쪽 방향이 벽도 아니고 아직 청소하지 않은 곳이면 왼쪽으로 회전하고, 그 칸으로 이동해 그 칸을 청소한다(2a). ..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 요즘 비슷한 문제를 엄청 많이 풀었다. 다 거기서 거기네.. bfs... 비슷한 bfs 문제들 경쟁적 전염 연구소 감시 피하기 인구 이동 make_ripe 함수로 하루동안 토마토의 변화를 계산한다. 우선 익은 토마토가 있는 좌표들인 tomato를 큐로 만들고, 이들을 하나씩 pop하면서 그 토마토의 인접한 부분 중에 0인 곳이 있으면 1로 바꿔준다. 그리고 이제 익게 되었으니 다음..