![]()
문제 링크 : https://www.acmicpc.net/problem/1248 1248번: 맞춰봐 문제 규현이는 멍청하다. 왜냐하면, 1~10까지 수 밖에 모르기 때문이다. 어느 날 규현이 옆을 지나가던 태석이가 규현이를 보고 이렇게 외쳤다. "빵빵!!" 규현이는 "아하!" 하면서 세상에는 빵이란 수도 있구나 했다. 그날 이후로 규현이는 매일 친구들을 볼 때면 "빵빵!!" 거리면서 인사를 했다. 규현이의 친구 중에는 태방이가 있다. 자꾸 규현이가 "빵빵!!" 거릴때 마다 자신을 놀리는 것 처럼 생각했던 태방이는 규현이에게 그건 "빵이 아니고 영이야" www.acmicpc.net 풀이 백트래킹 문제입니다! 이 문제는 서론이 좀 긴데 간단히 압축하자면, -10~10 까지의 정수로 채운 S배열이 있는데, S..
![]()
문제 링크 : https://www.acmicpc.net/problem/15661 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다. www.acmicpc.net 풀이 Brute force 문제 입니다! 이 문제는 선수들이 몇명씩 나뉘는지 모르기 때문에 순열로 풀 수 없고 팀을 두 개로 나눈 후 재귀호출을 통해서 선수들을 두 팀에 각각 집어 넣는 과정을 반복합니다. 이 때 재귀호출 함수의 인자로는 0~n까지 선수가 들어가는지에 대한 index와 두 팀의 선수들을 구성하는 ..
![]()
문제 링크 : https://www.acmicpc.net/problem/9019 9019번: DSLR 문제 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자) D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경 www.acmicpc.net 풀이 Bfs 문제입니다! 문제에 나와있듯 가지치기의 방법은 4가지가 있고, 출력에서 최소한의 명령어 나열을 요구했으므로 문..
![]()
문제 링크 : https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 www.acmicpc.net 풀이 bfs 문제입니다! 수빈이의 이동 방법이 3가지이고, n과 k의 범위가 0~10만 이기 때문에, 이 문제는 최대 10만..
![]()
문제 링크 : https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집도 이웃이다. 각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠하는 비용의 최솟값을 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 다이내믹 프로그래밍 문제입니다! RGB거리에 사는 사람들은 빨강, 초록, 파랑 3가지 색 중 하나로 집을 칠해야하는데, 인접한 집의 색이 같으면 안된다. 따라서 i번째 집의..
![]()
문제 링크 : https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 풀이 다이내믹 프로그래밍 문제입니다! 2X1 칸에 사자를 배치하는 경우는 왼쪽 사자 오른쪽 사자 사자 없음 세 가지이며, 사자들은 가로,세로에 붙어있을 수 없다. 각각의 경우를 0,1,2로 표현했을 경우 d[i][j] = i칸에 j상태의 사자가 있을 경우 사자 배치의 경우의 수 라고 표현 가능하며 각각 d[i][0] = d[i-1][1] + d[i-1][2] d[i][1] = d[i-1][0] + d[i-1][2] d[i][2] = d[i-1][0] + d[i-1][1] + d[i-1][2] 이다. 따라서 정답은 d..
![]()
문제 링크 : https://www.acmicpc.net/problem/17087 17087번: 숨바꼭질 6 수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다. 수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이동할 수 있다. 수빈이의 위치가 동생이 있는 위치와 같으면, 동생을 찾았다고 한다. 모든 동생을 찾기위해 D의 값을 정하려고 한다. 가능한 D의 최댓값을 구해보자. www.acmicpc.net 풀이 최대 공약수 문제입니다! 수빈이와 동생의 위치 차이를 v1,v2,...,vn 이라고 하면, 모든 동생을 찾기 위한 D의 값은 모든 v의 최대 공약수이어야 합니다. 따라서 이 문제는 모든..
![]()
문제 링크 : https://www.acmicpc.net/problem/17299 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 풀이 스택 문제입니다! 17298번 오큰수 문제랑 거의 비슷한 문제입니다. 17298번 오큰수 문제 참조 : https://suhwanc.tistory.com/58 다른 점은 미리 원소의 개수를 카운트 한다는 점인데, 이 카운트를 이용해 고대로~ stack 작업할 때 써먹으면 된다! 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 ..
![]()
문제 링크 : https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 풀이 스택을 이용하는 문제입니다! 우선 stack을 만든 후, 수열 A에 대해서 push를 계속 해줍니다. 단, stack.top() 보다 큰 수가 나왔을 경우 top 원소의 오큰수는 반드시 그 큰 수가 됩니다. 바로 오른쪽에 있는 수이기 때문이죠. 그렇게 오큰수가 정해진 원소는 pop해주고, 또 다시 비교를 반복해 top 원소가 그 수보다 클 때 까지 반복하고, 그 수를 push 합니다. (st..
![]()
문제 링크 : https://www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 풀이 DP(Dynamic programming) 문제입니다! bottom - up 방식으로 이 문제를 해결해보자면, 각 카드팩의 값을 p[1~n] 이라고 두면 카드 1개를 갖기 위한 금액의 최솟값(=d[1])은 p[1] 카드 2개를 갖기 위한 금액의 최솟값은 min(p[2],d[1]+p[1]) 카드 3개를 갖기 위한 금액의 최솟값은 min(p[3],d[2]+p[1],d[1]+p[2]) ..
![]()
문제 링크 : https://www.acmicpc.net/problem/17425 17425번: 약수의 합 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다. 자연수 N이 주어졌을 때, g(N)을 구해보자. www.acmicpc.net 문제 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3,..
![]()
문제 링크 : https://www.acmicpc.net/problem/17427 17427번: 약수의 합 2 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다. 자연수 N이 주어졌을 때, g(N)을 구해보자. www.acmicpc.net 문제 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, ..
