Problem Solving/BOJ51 [Python]5373. 큐빙 https://www.acmicpc.net/problem/5373 5373번: 큐빙 문제 루빅스 큐브는 삼차원 퍼즐이다. 보통 루빅스 큐브는 3×3×3개의 작은 정육면체로 이루어져 있다. 퍼즐을 풀려면 각 면에 있는 아홉 개의 작은 정육면체의 색이 동일해야 한다. 큐브는 각 면을 양방향으로 90도 만큼 돌릴 수 있도록 만들어져 있다. 회전이 마친 이후에는, 다른 면을 돌릴 수 있다. 이렇게 큐브의 서로 다른 면을 돌리다 보면, 색을 섞을 수 있다. 이 문제에서는 루빅스 큐브가 모두 풀린 상태에서 시작한다. 윗 면은 흰색, 아랫 면은 노란 www.acmicpc.net 큐빙 문제를 풀기전에 아래 문제를 먼저 풀어보자. https://br-brg.tistory.com/25 또한 큐빙 문제를 디버깅하는 동안 아.. 2019. 4. 11. [Python]16939. 2x2x2 큐브 https://www.acmicpc.net/problem/16939 16939번: 2×2×2 큐브 첫째 줄에 2×2×2 루빅스 큐브 각 면의 각 칸 색상이 주어진다. 색상은 1부터 6까지의 자연수로 나타내며, 각 자연수는 총 4번 등장한다. i번째 수가 의미하는 칸은 아래와 같다. www.acmicpc.net 5373. 큐빙을 풀기전에 미리 풀어보면 좋은 문제이다. 여기서 pitch, yaw, roll 은 3차원 축에 대한 회전방향을 나타내는 용어이다. 또한 큐브의 경우 한방향으로 3번 회전하는 것은 곳 1번 반대방향으로 회전한 것과 같다. 따라서 코드는 다음과 같다. ccw는 반시계방향, cw는 시계방향이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 2.. 2019. 4. 10. [Python]16235. 나무 재테크 https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 떨어진 칸의 개수, c는 가장 왼쪽으로부터 떨어진 칸의 개수이다. r과 c는 1부터 시작한다. 상도는 전자통신공학과 출신답게 땅의 양분을 조사하는 로봇 S2D2를 만들었다. S2D2는 1×1 크기의 칸에 들어있는 양분을 조사해 상도에게 전송하고, 모든 www.acmicpc.net 이 문제는 시뮬레이션 문제로 문제를 분석해서 코드를 짜는데 크게 어렵진 않았다. 다만 나무를 1차원 리스트로 통째로 관리해서 푼다면.. 2019. 4. 10. [Python]16236. 아기 상어 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크 www.acmicpc.net BFS + 약간의 시뮬레이션 문제라고 생각한다. 누구는 BFS만으로도 푼다. 코드구현은 한시간 걸린듯 한데 디버깅이 너무너무너무 오.. 2019. 4. 9. [Python]6064. 카잉 달력 https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 문제 최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 로 표현하고, 두 번째 해를 로 표현하였다. 의 다음 해를 표현한 것을 이라고 하자. 만일 www.acmicpc.net 그냥 브루트포스로 구현하면 최대 경우의 수가 40000^2 으로 제한시간내에 통과할 수 없다. 규칙을 찾아서 연산해서 값을 구해야 한다. 전체 경우의 수를.. 2019. 4. 9. [Python]17136. 색종이 붙이기 https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐 www.acmicpc.net 두번째로 풀어본 상시 역량테스트 기출문제. 어려웠다. 아직도 실력이 많이 부족한 것같다. ㅜㅜ 고사장에 있을 때 DFS로 하면 되겠다고 생각하긴 했었지.. 2019. 4. 8. [Python]1107. 리모컨 https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러번 주어지는 경우는 없다. www.acmicpc.net 브루트포스로 접근 Step1.먼저 0~1,000,000 까지 수를 생성한다 Step2.생성된 수 중에서 고장난 숫자를 포함하고 있으면 버린다. 고장난 수를 포함하지 않으면 channels 에 추가한다. Step3.channels에서 가장 최소값을 구한다 Step4.현 위치(100)에서의 눌러야 하는 값과 Step3에서 구한 최.. 2019. 4. 8. [Python]2225. 합분해 https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 2차원 DP로 접근하면 쉽게 해결할 수 있는 문제였다. 조건에서 0 2019. 4. 8. [Python]1699. 제곱수의 합 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 www.acmicpc.net dp[i-1] 이 아닌 dp[i-j^2] 을 이용해서 제곱수의 합을 DP로 구현하는 것이 포인트. dp[i] = min(dp[i-j^2.. 2019. 4. 7. 이전 1 2 3 4 5 6 다음 728x90 반응형
