https://www.acmicpc.net/problem/4673 4673번: 셀프 넘버 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, www.acmicpc.net for문을 두번 돌면서 각 숫자로 하여금 생성될 수 있는 "셀프 넘버가 아닌 것" 들을 구해서 저장한다. 2개의 for문을 통해, 셀프 넘버가 아닌 것들을 True로 바꿔서 False인 것들(=셀프 넘버)만 출력해주면 된다. set을 이용한 깔끔한 코드도 있다고 하니, 문제를 다 풀고 나서 찾아보시길! import sys import math fr..
https://www.acmicpc.net/problem/27211 27211번: 도넛 행성 준겸이는 $N \times M$칸으로 이루어진 도넛 모양의 행성에 살고 있다. 준겸이가 살고 있는 행성에는 위 그림처럼 격자 모양으로 줄이 그어져 있다. 행성의 각 칸은 숲으로 막혀 있거나, 지나갈 수 www.acmicpc.net 조금 지저분하게 푼 것 양해바랍니다,, 우선, 보드의 크기와 입력은 고정되어있으므로 선언해준 뒤 시작한다. 이때 10x10 이라고 무조건 2차원 배열로 만들 필요는 없다! 주사위는 +1 ~ +6까지 무조건 양의 방향으로만 증가하므로 1차원 배열로 선언해주어야 더 쉽게 풀 수 있다. 사다리와 뱀의 정보도 구별 지을 필요 없다. 어찌됐건 둘 다 만나면 다른 곳으로 이동하므로 하나의 리스트에..
https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 2048게임을 구현하는 문제이다. 실제 2048과 다른 점은, 움직일 때 새로운 블럭이 생성되지 않는다는 점이고 이동횟수가 5번으로 제한되어있다는 것이다. 전체적인 구성은 기본적인 dfs방식을 이용한 백트래킹+브루트포스와 동일하다. 다만 상,하,좌,우 이동 시 블럭들을 처리하는 것이 조금 까다롭다. 키포인트는 다음과 같다. 1. 합쳐지는 방향대로 각 열 또는 행들을 배..
https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 점수가 큰 과제를 많이 먹어야하는데, 마감 기간을 잘 고려해서 스켸쥴을 짜면 된다. 우선 점수가 큰 순으로 정렬한 뒤, 이제 스켸쥴 표를 하나씩 채워나가면 된다. 해당 위치에 이미 값이 있으면 (= 그날 할 과제, 즉 계획이 있으면) 앞으로 날짜를 당기면서 빈 곳에 계획을 채워넣는다. 결국, 1 ~ m일차까지의 스켸쥴 표를 작성한다고 생각하면 쉽다! (여기서 m은 과제 마감일 중 제일 큰 값, 코드에서 cnt값) import sys sys...
https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 중복조합 또는 dp로 해결가능한 문제인데, dp로 풀어보았다. 우선, k가 1일 경우엔 n으로 어떤 수가 와도 경우의 수는 1이다. 그러나 n이 1일 경우, 경우의 수는 k값을 따라간다. dp 테이블 k = 1 k = 2 k = 3 n = 1 1 2 3 n = 2 1 3 n = 3 1 n = 4 1 n = 5 1 이제 위 dp 테이블을 채워나가면 된다. n=2이고 k=2일 때 가능한 경우는 0+2, 2+0, 1+1 총 3가지 이다. 이는 (2,1)의 경우인 2와 (1,2)의 경우인 0+1, 1+0를 합한 것이라고 볼 수 있..
https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 최소신장트리(MST)를 만드는 알고리즘을 약간 응용한 문제이다. 우선 주어진 입력을 바탕으로 MST를 생성한다.(프림 또는 크루스칼 이용) 문제에서 요구하는 조건을 만족하기 위해서는, 생성된 최소신장트리에서 간선의 비용이 가장 큰 것을 하나 찾은 뒤 그곳을 기점으로 잘라주면(=간선을 제거하면) 문제의 조건을 충족시킬 수 있다. #include using nam..
