본문 바로가기

백준

[백준][11052번, 16194번][Python] 카드 구매하기 1,2 && 블로그 닉값의 위험성 주의! 이 문제는 블로그 닉네임 값을 한 문제이며 닉값하지 말자는 반성문입니다. 두 문제의 차이는 간단하다. 최대를 구하냐, 최소를 구하냐 정도뿐이다. dp문제에서 dp배열을 초기화할때는 (나는) 값을 0으로 한다. 별 의미도 모르는채로 초기화한다. 방법은 다음과 같다. dp[n] = n개의 카드를 샀을때의 최댓값, 최솟값을 구한다. for i in range(1,n+1): for j in range(1,i+1): dp[i] = max(dp[i], dp[i-j]+arr[j]) 이때, 이 문제는 i 개의 카드를 살때 최댓값을 구하는 첫번째 반복문과, 1 16149 은 i번째 까지 샀을때는 == j번째 카드팩을 샀을때 값이 최대/최소가 될까? 를 판별하는 식이다. 이건 간단한데, 여기서 닉값을 했다가 시간을.. 더보기
[백준][Python][10942][DP] 팰린드롬? 문제 : https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net DP 문제다. 문제의 핵심은 길이가 1,2, 그 이상일때의 경우를 각각 나누는 것이다. (1은 참 0은 거짓이라 하자) dp 배열은 dp[처음][끝] -> 처음 - 끝까지 했을 때 팰린드롬 인가? 이다. 길이가 1 = 무조건 1 길이가 2 = 두 문자가 같으면 1 길이가 3 이상 -> 처음 문자 == 끝 문자 && dp[처음+1][마지막-1] 이 1 import sys n = int(input()) d = [int(i) for.. 더보기
[백준][Python][1890][DP]점프 문제 : https://www.acmicpc.net/problem/1890 1890번: 점프 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 www.acmicpc.net DP 길 갯수 문제 변형이다. 입력받는 배열의 원소는 그 자리에 갔을 오른쪽이나 아래로 점프를 해야되는 칸 의 갯수이다. 이 문제는 .. 더보기
[백준][Python][3190][브루트포스] 뱀 문제 : https://www.acmicpc.net/problem/3190 3190번: 뱀 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따 www.acmicpc.net 최적화와 기타등등 아무것도 신경안쓴 누더기 코드를 보는 당신! 축하드립니다. 잘난 코드는 다들 비슷하지만 못난 코드는 개성있게 못났다는.. 더보기
[백준][9095][Python][DP] 1,2,3 더하기 문제 : https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각 www.acmicpc.net 간단한 DP 문제다. 1,2,3 더하기 시리즈 문제를 보면, 여러 제약조건이 생기면서 (같은 번호 2개이상 붙이면 안.. 더보기
[백준][Python][10971][브루트포스] 외판원 순회 2 문제 : https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다. www.acmicpc.net 외판원 순회 Traveling Salesman problem 는 유명한 NP-Complete 문제다. O(N!)의 어마어마한 복잡도를 가지는 문제이므로 순열도 부담없이 사용했다. 문제 풀이는 다음과 같다. 1-n 사이의 모든 순열을 만든다. 수열 하나하나마다: 1-2.. 더보기
[백준][Python][11057][DP] 오르막 수 문제 : https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다. www.acmicpc.net 이 문제는 고생 많이한 문제다. 문제의 해결법은 다음과 같다. d[i] 를 i+1 번째 자릿수의 앞자리 로 하자. 1자리 숫자들은 전부 오르막 수로 볼수 있기 때문에 1로 초기화한다. 이제 생각해보면 12,13,14.. 23,24,25..등등은 전.. 더보기

티스토리툴바