구름을 채우다

문제 보기이 문제는 동적계획법(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..

문제 보기예전에 오답처리를 2번 받고나서 귀찮아서 안 푼 문제인 것 같다.문제 해결을 위한 방법은 매우 간단하다.어린 왕자가 출발점에서부터 도착점까지 최소한의 행성계의 이탈/진입 횟수를 측정하는 것인데, 이는 한 가지의 조건만 안다면 해결할 수 있다. 핵심 조건은 각 행성계를 기준으로, 출발점과 도착점 서로 행성계의 안팎으로 다른 위치에 있어야 한다는 것이다. 위의 그림에 해당하는 조건을 만족하는 행성계의 갯수를 세면 정답이다. 소스코드에서 위의 조건에 해당하는 조건문은 19번째 줄이다.점과 점 사이의 거리를 측정하기 위해서 원래 sqrt를 써야하지만, 나는 sqrt를 쓰지 않는 대신 행성계의 반지름의 길이를 제곱해서 비교하였다. 12345678910111213141516171819202122import..

문제보기 이 문제는 문제에서 요구하는 순서에 따라 코딩하면 되는 시뮬레이션 문제이다. 문제만 읽어보면 아주 쉬운 문제이지만, 나는 어디서 잘못됐는지 한동안 풀지 못했었다. 아직 많이 미숙한 것 같다. 코드 상에서 눈여겨 볼 점은, 로봇의 작동 순서 중 2-2단계가 없다는 것이다. 코드에서 2번째 while문은 로봇이 네 방향을 모두 탐색하면서 청소를 하기 위한 while문이다. 30번째 줄을 보면 nextDir = (nextDir + 3) % 4 부분이 있는데, 로봇이 보고있는 현재 방향에서 왼쪽을 탐색하는 게 아니라, 탐색할 방향만을 계속해서 바꾸는 것을 알 수 있다. (그리고 나중에 현재 로봇의 방향과 같다는 조건을 비교하면 네 방향을 모두 탐색했다는 뜻이 된다.) 이로써 2-2단계의 코드는 생략할 ..

문제보기해당 문제는 브루트포스와 BFS를 조합한 문제이다.문제를 풀기 위해, 세워야 하는 벽의 갯수는 반드시 3개여야 하며, 안전 영역 크기의 최댓값을 구해야 한다. 이를 통해서 벽을 세울때는 반드시 겹치면 안되며, 벽의 위치의 조합을 구해야 하고, 해당 조합은 안전구역에서 겹치지 않는 3개의 위치여야 한다는 것을 알 수 있다..게다가 주어진 입력값의 범위가 크지 않은 3