구름을 채우다

문제 보기이 문제는 동적계획법(Dynamic Programming) 문제이다.아주 쉬운 문제이지만, DP에 익숙하지 않아서 고민을 많이 했다.풀이는 다음과 같다. 1. 내일 벌 돈이 오늘 번 돈보다 적다면 이를 갱신한다.2. 오늘 일을 하면 오늘로부터 time[i]번째 날에 돈을 받는다.3. 오늘 일을 해서 time[i]번째날 후에 받을 수 있는 돈이 현재 time[i]번째 날에 받을 수 있는 돈의 최대값보다 크다면 이를 갱신한다. 123456789101112131415161718import sys n = int(sys.stdin.readline())time = [0 for _ in range(n)]price = [0 for _ in range(n)]dp = [0 for _ in range(n + 1)]..

문제 보기이 문제는 브루트 포스 문제이다. (DFS로도 풀 수 있다.)위의 도형들을 회전, 대칭하여 만들 수 있는 총 블록들을 리스트에 저장하여, 종이의 각 칸에 방문할때마다 최대값을 찾는다. 다른 풀이를 보아하니, 보라색 테트로미노를 제외하고는 모두 DFS로 탐색 가능한 도형이다.보라색을 제외한 모든 테트로미노들을 DFS로 탐색할 시, 모두 Depth가 3이다.종이 위의 모든 칸을 순회하면서, DFS로 Depth가 3인 테트로미노와 보라색 테트로미노의 경우의 수 4가지를 비교해서 최대값을 구하면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041import sys n, m = map(int, sys.stdin.rea..

문제 보기이 문제는 단순구현 문제이다.단지 주사위를 굴렸을 때 어떻게 주사위의 각 면들을 구할 것인지, 지도와 주사위의 밑바닥 값을 어떻게 복사할 지 주의하면 된다. 첫번째로, 주사위를 상하좌우로 굴려서 면이 바뀌었을 때, 이를 업데이트 하는 방법은 다음과 같다.주사위의 전개도에서 각 위치들을 절대적인 위치로 생각하고, 주사위를 굴렸을 때 바뀐 면들을 업데이트 한다.이를 구현하면 아래와 같다. (전개도는 절대적인 명시되있는 것처럼 절대적인 위치라고 생각한다.) 두번째로, 주사위를 굴릴 다음 위치가 지도에 없으면, 해당 움직임은 무시 해야한다.만약 주사위를 성공적으로 굴렸다면, 문제에서 지시하는대로 값을 복사하면 된다. 123456789101112131415161718192021222324252627282..

문제 보기이 문제는 단순구현 문제이다.문제가 매우 쉽다고 생각하고, 각 방마다 필요한 감독관의 수를 구해서 총 합을 구했는데 WA를 받았다.질문게시판을 찾아보니, 한 방안에 있는 시험자의 수가 총 감독관이 감독할 수 있는 수보다 적으면 음수가 되는데, 이를 처리하지 않아서 WA를 받았던 것이다.이를 처리해주니 AC를 받았다. 123456789101112131415161718import sys n = int(sys.stdin.readline())tester = list(map(int, sys.stdin.readline().split()))b, c = map(int, sys.stdin.readline().split()) answer = 0for i in range(n): tester[i] -= b if te..

문제 보기이 문제는 시뮬레이션 문제이다.이 문제를 풀어보니 시뮬레이션에 많이 취약한 것 같다.시뮬레이션 문제는 적혀있는 그대로 구현하는 것이 어려운 게 아니라, 요구사항을 정확히 이해하고 구현하는게 제일 중요한 것 같다. 다음과 같이 문제의 요구사항이 있다.문제에서 요구하는대로 구현하는 것이 어렵지만, 문제의 구현에 집중하다보니 간과한 부분이 있다.입력의 조건에 보면, 다음과 같이 명시되어 있다.사과의 위치는 모두 다르며, 맨 위 맨 좌측 (1행 1열)에는 사과가 없다.즉, 뱀이 시작하는 위치는 (1, 1)로 생각하고 문제를 풀어야 한다는 것이다.이에 주의해서 구현하면 AC를 받을 수 있다. (내 코드로는 메모리와 시간이 꽤나 걸린다.. 추후에 더 개선 해야겠다.) 123456789101112131415..

문제 보기이 문제도 BFS와 브루트 포스를 합친 문제이다.처음에 문제를 읽었을 때, 완전탐색을 해야하지만 무엇을 완전탐색 해야할 지 감이 잡히지 않았다.계속 고민을 하다보니, 상, 하, 좌, 우로 블록들을 이동시켰을 때의 판의 상태를 완전탐색해야겠다고 생각했다. BFS 부분은 그래프 내에서 최대값을 구하는 알고리즘과 동일하다. 구현 상의 어려운 부분은 moveBoard 메소드인데, 블록들을 이동시켰을 때의 상태를 새로운 판 객체로 반환해서, 이를 큐에 추가하는 것이다. 문제는 최대 5번 이동시켜서 얻을 수 있는 최댓값을 구하는 것이기 때문에, 5번이 넘어가면 BFS를 중단하고 결과값을 반환한다. 판 객체를 큐에 추가한다는 개념은 아래의 그림을 보면 이해하기 쉽다. 위 그림은 블록들을 1번 이동시켰을 때의..

문제 보기이 문제는 BFS에 브루트포스를 응용한 문제이다.처음에 문제를 읽을 당시에는 어떻게 코드를 짜야할 지 몰랐지만, 질문게시판을 뒤지다 보니 영감을 얻었다.한 번 방문할 때마다 각 방향을 탐색하는 건 기존의 BFS 동일하다.하지만 판을 기울일 때 벽, 구멍 또는 다른 공에 닿을 때까지 직진을 해야한다는 것에 주의해야 한다. 또 주의해야할 점은, 두 개의 공을 굴려서 같은 곳에서 멈추는 경우에는, 공이 굴러간 거리를 계산한 뒤, 굴러간 거리가 더 긴 공을 다시 굴러왔던 방향으로 1번 이동해야 한다. (그렇게 해야 공이 겹치지 않는다. 60~65번째 줄 참고) 67~69번째 줄을 보면 다음과 같은데, 이 부분의 코드가 없으면 count가 11이상이 되는 반례가 생긴다. # prevent count fr..