본문 바로가기

백준풀이31

[Python] 백준 1562 계단 수 문제45656이란 수를 보자.이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.N이 주어질 때, 길이가 N이면서 0부터 9까지 숫자가 모두 등장하는 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. 0으로 시작하는 수는 계단수가 아니다.https://www.acmicpc.net/problem/1562       난이도골드 1      코드import sysn = int(sys.stdin.readline())dp = [[[0 for _ in range(2**10)] for _ in range(10)] for _ in range(n+1)]answer = 0mod = 1000000000for j in range(1,10) : dp[1][j][1 0 : .. 2024. 10. 17.
[Python] 백준 1799 비숍 문제서양 장기인 체스에는 대각선 방향으로 움직일 수 있는 비숍(bishop)이 있다. 과 같은 정사각형 체스판 위에 B라고 표시된 곳에 비숍이 있을 때 비숍은 대각선 방향으로 움직여 O로 표시된 칸에 있는 다른 말을 잡을 수 있다. 그런데 체스판 위에는 비숍이 놓일 수 없는 곳이 있다. 에서 체스판에 색칠된 부분은 비숍이 놓일 수 없다고 하자. 이와 같은 체스판에 서로가 서로를 잡을 수 없도록 하면서 비숍을 놓는다면 과 같이 최대 7개의 비숍을 놓을 수 있다. 색칠된 부분에는 비숍이 놓일 수 없지만 지나갈 수는 있다.  정사각형 체스판의 한 변에 놓인 칸의 개수를 체스판의 크기라고 한다. 체스판의 크기와 체스판 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 주어질 때, 서로가 서로를 잡을 수 없는.. 2024. 10. 15.
[Python] 백준 1509 팰린드롬 분할 문제세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다.분할의 개수의 최솟값을 출력하는 프로그램을 작성하시오.https://www.acmicpc.net/problem/1509      난이도골드 1        코드import sysdef palin() : for i in range(n) : isPal[i][i] = True for i in range(2,n) : ii = i for j in range(1,n+1-i) : if x[ii] == x[j] : .. 2024. 10. 15.
[Python] 백준 17387 선분 교차 2 문제2차원 좌표 평면 위의 두 선분 L1, L2가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있는 것도 교차하는 것이다.L1의 양 끝 점은 (x1, y1), (x2, y2), L2의 양 끝 점은 (x3, y3), (x4, y4)이다.https://www.acmicpc.net/problem/17387     난이도골드 2     코드import sysdef CCW(a1,b1,a2,b2,a3,b3) : ccw = (a2-a1) * (b3-b1) - (b2-b1) * (a3-a1) return ccwx1,y1,x2,y2 = map(int,sys.stdin.readline().split())x3,y3,x4,y4 = map(int,sys.stdi.. 2024. 10. 11.
[Python] 백준 16946 벽 부수고 이동하기 4 문제N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다.각각의 벽에 대해서 다음을 구해보려고 한다.벽을 부수고 이동할 수 있는 곳으로 변경한다.그 위치에서 이동할 수 있는 칸의 개수를 세어본다.한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.    난이도골드 2    코드import sysfrom collections import dequen, m = map(int,sys.stdin.readline().split())graph = []group_width = [0,0] # 그룹번호의 너비를 담는 리스트group_nu.. 2024. 10. 10.
[Python] 백준 12015 가장 긴 증가하는 부분 수열 2 문제수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.https://www.acmicpc.net/problem/12015        난이도골드2    내 코드import sysdef binarySearch(value) : left = 0 right = len(lis) - 1 while left value : right = mid - 1 else : left = mid + 1 return leftn = int(sys.. 2024. 10. 9.

티스토리툴바