본문 바로가기

전체 글133

[백준 2156] 포도주 시식, C++ https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고 www.acmicpc.net 본 문제는 1 ~ n까지의 포도주 잔에 들어있는 포도주 양이 각각 다를 때, 가장 많은 양의 포도주를 마시는 방법을 구하는 문제다. .. 2020. 1. 14.
[백준 1212] 8진수 2진수, C++ https://www.acmicpc.net/problem/1212 1212번: 8진수 2진수 첫째 줄에 8진수가 주어진다. 주어지는 수의 길이는 333,334을 넘지 않는다. www.acmicpc.net 본 문제는 8진수를 2진수로 변환하는 문제다. string으로 입력받는다. 2진수로 변환한다. 3자리 문자열로 2진수를 저장한다. 앞자리가 0이 아닐 때까지 찾는다. 출력 주의점 : 8진수 0이 입력되었을 때, 4의 과정 때문에 출력이 안된다. 따라서, 8진수 0을 예외 처리한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 .. 2020. 1. 13.
[백준 1373] 2진수 8진수, C++ https://www.acmicpc.net/problem/1373 1373번: 2진수 8진수 첫째 줄에 2진수가 주어진다. 주어지는 수의 길이는 1,000,000을 넘지 않는다. www.acmicpc.net 본 문제는 2진수를 8진수로 변환하는 문제다. 이때, string으로 변환해서 풀면 쉽게 풀린다. 프로그래머스에 이런 문제가 많아서 큰 도움이 됐다. string으로 입력 자릿수를 3으로 나누어 떨어지게 만들기 3자리씩 8진수로 변환하기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 #include #include #include #include #include using namespace std; in.. 2020. 1. 13.
[백준 17087] 숨바꼭질 6, C++ https://www.acmicpc.net/problem/17087 17087번: 숨바꼭질 6 수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다. 수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이동할 수 있다. 수빈이의 위치가 동생이 있는 위치와 같으면, 동생을 찾았다고 한다. 모든 동생을 찾기위해 D의 값을 정하려고 한다. 가능한 D의 최댓값을 구해보자. www.acmicpc.net 본 문제는 수빈이가 동생 N명을 찾는 문제다. 수빈이의 위치를 X라고 했을 때, X+D, X-D로 이동할 수 있다. 따라서, 동생과 수빈이의 위치의 차를 구해야 하고, D의 최댓값을 구해야 하므로 수빈이의.. 2020. 1. 13.
[백준 9613] GCD 합, C++ https://www.acmicpc.net/problem/9613 9613번: GCD 합 문제 양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진다. 입력으로 주어지는 수는 1000000을 넘지 않는다. 출력 각 테스트 케이스마다 가능한 모든 쌍의 GCD의 합을 출력한다. 예제 입 www.acmicpc.net 본 문제는 2013 ACM-ICPC Asia Phuket Regional Programming Contest PE번 문제로 양의 정수 .. 2020. 1. 13.
[백준] 2225 - 합분해, C++ https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 본 문제는 0 ~ N까지 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 문제다. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 큰 문제를 작은문제로 나누어 해결할 수 있기 때문에 DP문제이고, d[n][k] = d[n-0][k-1] + d[n-1][k-1] + d[n-2][k-1] + ... + d[n-n][k-1] 으로 점화식을 정의 할 수 있다. Bottom-up 방법을 사용하였고, 미지수가 3개이므로 3중 for문을 사용했다. 사실 DP를 풀기전에 완전탐색을 이용하여 해.. 2020. 1. 13.
[백준] 1699 - 제곱수의 합, C++ https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 www.acmicpc.net 본 문제는200 7 ICPC Seoul Nationalwide Internet Competition E번 문제로 주어진 자연수 N을 제.. 2020. 1. 12.
[백준] 1912 - 연속합, C++ https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 본 문제는 분류상 DP로 나와 있지만 완전 탐색 문제라고 생각한다. 한 가지 주의해야 할 점은 최댓값을 비교할 때, 0보다 작은 경우가 있을 수 있으므로 충분히 큰 음의 값을 선언한다. a[i] > a[i-1] + a[i] 일 때, continue 그 외, a[i] = a[i-1] + a[i] 최댓값 출력 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 .. 2020. 1. 12.
[백준 14002] 가장 긴 증가하는 부분 수열 4, C++ https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net 본 문제는 가장 긴 증가하는 부분 수열과 비슷한 문제다. (때문에 자세한 설명은 생략한다.) 가장 긴 증가하는 부분 수열의 길이를 출력하는 것은 동일하나, 가장 긴 증가하는 부분 수열을 출력해야 하는 문제다. 따라서, 점화식을 계산할 때 따로 이전 배열만 저장하면 된다. Bottom-up 1 2 .. 2020. 1. 12.

티스토리툴바