목록2024/02 (6)
-
문제 https://www.acmicpc.net/problem/2116 2116번: 주사위 쌓기 첫줄에는 주사위의 개수가 입력된다. 그 다음 줄부터는 한 줄에 하나씩 주사위의 종류가 1번 주사위부터 주사위 번호 순서대로 입력된다. 주사위의 종류는 각 면에 적혀진 숫자가 그림1에 있는 www.acmicpc.net 풀이 방법 주사위의 개수와 주사위 정보를 입력받는다. 가장 밑에 오는 주사위에서 밑면을 무엇으로 해야 최대가 되는지 계산하기 위해 for 문을 1 - 6까지 돈다. 밑에 있는 주사위의 윗면과, 위에 있는 주사위의 밑면이 일치해야하기 때문에 그 수를 맞춘 상태에서 옆면이 최대가 되는 숫자를 더해준다. for 문이 끝날 때마다 최대가 되는 옆면의 합을 갱신한다. 코드 n = int(input()) d..
문제 https://www.acmicpc.net/problem/16922 16922번: 로마 숫자 만들기 2, 6, 10, 11, 15, 20, 51, 55, 60, 100을 만들 수 있다. www.acmicpc.net 풀이 방법 로마숫자를 더해서 나오는 수에 해당하는 인덱스 (예를 들어 로마숫자 IX → 11) 에 1을 더해준다. 나중에 로마숫자로 만들 수 있는 숫자의 총 개수를 sum 함수로 쉽게 세기 위함이다. 재귀함수를 사용해서 숫자를 반복적으로 더해준다. 코드 n = int(input()) roma = [1, 5, 10, 50] arr = [0] * 1001 num = 0 def dfs(cur, start): global num if cur == n: arr[num] = 1 return for ..
문제 https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 방법 지나갈 수 있는 길인지 체크할 때, 높이가 같은 경우 : 그냥 넘어감 높이가 2 이상 차이 나는 경우 : False 반환 왼쪽이 더 높은 경우 : 경사로를 놓을 공간이 있는지 체크 후 경사로 설치 오른쪽이 더 높은 경우 : 경사로를 놓을 공간이 있는지 체크 후 경사로 설치 로 나눠서 풀어야 한다. 이 때, 경사로를 설치한 곳에는 중복해서 설치할 수 없기 때문에 bridge 라는 리스트를 만들어 해당 위치..
문제 https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 풀이 방법 n = 3 일 때, 전체 9칸을 차례대로 돌면서 주변에 있는 내가 원하는 번호의 개수와, 빈 자리를 체크하여 리스트에 저장한다. 문제에서 주어진 조건에 맞게 자리 배치를 하기 위해 lambda 함수를 사용해 리스트를 정렬하는데, 원하는 번호의 개수와 빈자리를 내림차순으로, 행과 열을 오름차순으로 정렬한다. 이렇게 정렬을 마쳤으면 가장 첫 번째 오는 원소에 있는 행과 열에..
문제 https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 풀이 방법 s → t 를 만드는 것은 경우의 수가 너무 많기 때문에 시간 복잡도 측면에서 비효율적이다. 따라서 t → s 를 만드는 것이 낫다. 기존 방법 문자열의 뒤에 A를 추가한다. 문자열을 뒤집고 뒤에 B를 추가한다. 반대 방법 문자열의 끝에 있는 A를 제거한다. 문자열 끝에 있는 B를 제거하고 문자열을 뒤집는다. 만약 t → s 변환이 성공하면 1..
문제 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 풀이 방법 외부 공기와 두 칸 이상 맞닿으면 다음 턴에 치즈가 녹지만, 내부 공기와 맞닿으면 녹지 않는다. 따라서 기존에 0이었던 외부 공기를 모두 2로 바꿔주는 작업이 필요하다. 외부 공기를 모두 2로 바꿔주었으면, 두 칸 이상의 외부 공기와 맞닿은 치즈를 체크해서 2로 바꿔준다. (녹은 것) 반복한다. 코드 import sys sys.setrecursionlimit(10**6..