알고리즘 풀이
-
백준(BOJ) 11048번 이동하기알고리즘 풀이/백준(Boj) 2019. 7. 3. 22:16
문제: https://www.acmicpc.net/problem/11048 입력첫째 줄에 미로의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 1,000)둘째 줄부터 N개 줄에는 총 M개의 숫자가 주어지며, r번째 줄의 c번째 수는 (r, c)에 놓여져 있는 사탕의 개수이다. 사탕의 개수는 0보다 크거나 같고, 100보다 작거나 같다.출력첫째 줄에 준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수를 출력한다. 나의풀이 :완전탐색의 경우 탐색했던 경로를 또 탐색해야 하니 시간초과가 되었고 따라서 각 부분 문제를 최적으로 풀고 그 결과를 cache에 저장해 둠으로써 경로의 중복을 없앴다. 완전탐색 #include #include using namespace std;const int MAX = ..
-
백준(BOJ) 2529번 부등호알고리즘 풀이/백준(Boj) 2019. 7. 2. 01:43
문제: https://www.acmicpc.net/problem/2529 입력 첫 줄에 부등호 문자의 개수를 나타내는 정수 k가 주어진다. 그 다음 줄에는 k개의 부등호 기호가 하나의 공백을 두고 한 줄에 모두 제시된다. k의 범위는 2 ≤ k ≤ 9 이다. 출력 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다. 나의 풀이: 완전탐색으로 풀어보았다. 부등호 2개라면 2개를 기준으로 처음 0~9 고르고 / 부등호 / (앞에 부등호 보고) 0~9 고르고 / 부등호 / (앞에 부등호 보고) 0..
-
와일드카드알고리즘 풀이/알고리즘 해결전략 연습 2019. 7. 1. 01:07
알고스팟 문제 : https://algospot.com/judge/problem/read/WILDCARD algospot.com :: WILDCARD Wildcard 문제 정보 문제 와일드카드는 다양한 운영체제에서 파일 이름의 일부만으로 파일 이름을 지정하는 방법이다. 와일드카드 문자열은 일반적인 파일명과 같지만, * 나 ? 와 같은 특수 문자를 포함한다. 와일드카드 문자열을 앞에서 한 글자씩 파일명과 비교해서, 모든 글자가 일치했을 때 해당 와일드카드 문자열이 파일명과 매치된다고 하자. 단, 와일드카드 문자열에 포함된 ? 는 어떤 글자와 비교해도 일치한다고 가정하며, * 는 0 글자 이상의 어떤 문자 algospot.com 입력 입력의 첫 줄에는 테스트 케이스의 수 C (1
-
외발 뛰기알고리즘 풀이/알고리즘 해결전략 연습 2019. 6. 30. 03:55
문제 : https://algospot.com/judge/problem/read/JUMPGAME algospot.com :: JUMPGAME 외발 뛰기 문제 정보 문제 땅따먹기를 하다 질린 재하와 영훈이는 땅따먹기의 변종인 새로운 게임을 하기로 했습니다. 이 게임은 그림과 같이 n*n 크기의 격자에 각 1부터 9 사이의 정수를 쓴 상태로 시작합니다. 각 차례인 사람은 맨 왼쪽 윗 칸에서 시작해 외발로 뛰어서 오른쪽 아래 칸으로 내려가야 합니다. 이 때 각 칸에 적혀 있는 숫자만큼 오른쪽이나 아래 칸으로 움직일 수 있으며, 중간에 게임판 밖으로 벗어나면 안 됩니다. 균형을 잃어서 다른 발로 서거 algospot.com 입력: 입력의 첫 줄에는 테스트 케이스의 수 C(C > C; while (C--) { m..
-
울타리 잘라내기알고리즘 풀이/알고리즘 해결전략 연습 2019. 6. 29. 00:03
알고스팟 문제: https://algospot.com/judge/problem/read/FENCE algospot.com :: FENCE 울타리 잘라내기 문제 정보 문제 너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체하기로 했습니다. 이 때 버리는 울타리의 일부를 직사각형으로 잘라내 재활용하고 싶습니다. 그림 (b)는 (a)의 울타리에서 잘라낼 수 있는 많은 직사각형 중 가장 넓은 직사각형을 보여줍니다. 울타리를 구성하는 각 판자의 높이가 주어질 때, 잘라낼 수 있는 직사각형의 최대 algospot.com 입력 첫 줄에 테스트 케이스의 개수 C (C≤50)가 주어집니다. 각 테스트 케이스의 첫 줄에..
-
백준(BOJ) 1946번: 신입 사원알고리즘 풀이/백준(Boj) 2019. 6. 28. 23:01
문제링크: https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성적, 면접 성적의 순위가 공백을 사이에 두고 한 줄에 주어진다. 두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정한다. www.acmicpc.net 나의 풀이: 서류 성적순으로 정렬한다. 1등을 뽑은 후(cnt++) 1등의 면접 성적보다 높은 순위의 지원자를 고른다. (반복) 그 지원자를 뽑은후(cnt++) N까지 그 지원자의 면접성적보다 높은 순위의 지원자를 고른다. 주의할점..
-
백준(BOJ) 10815번: 숫자 카드알고리즘 풀이/백준(Boj) 2019. 6. 28. 22:10
문제링크: https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이가 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 www.acmicpc.net 입력: 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이가 주어진다. 둘째 줄에는 숫..