본문 바로가기

전체 글

 (248)
[C++] 백준 4641번 : Doubles (B1) #문제 https://www.acmicpc.net/problem/4641 4641번: Doubles 문제 2~15개의 서로 다른 자연수로 이루어진 리스트가 있을 때, 이들 중 리스트 안에 자신의 정확히 2배인 수가 있는 수의 개수를 구하여라. 예를 들어, 리스트가 "1 4 3 2 9 7 18 22"라면 2가 1의 2배, 4� www.acmicpc.net #풀이 이러한 유형의 문제가 처음 이해가 잘 되지 않았다. 그 이유는 이와 같은 입출력 예시를 보고 왼쪽의 숫자들의 입력이 모두 끝나면 오른쪽과 같이 출력이 돼야 한다고 생각했기 때문이다. 하지만 "각 테스트 케이스마다 한 줄에 걸쳐 정답을 출력한다."라는 의미는 다음과 같았다. 테스트 케이스를 입력할 때마다 정답이 출력되는 형태인 것이다. 이와 비슷한 ..
[C++] 백준 1065번 : 한수 (S4) #문제 https://www.acmicpc.net/problem/1065 1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 �� www.acmicpc.net #풀이 문제에서 N이 1000 이하의 자연수라고 하였으므로 경우를 그냥 나누어 문제를 풀 수 있다. 우선 1부터 99까지는 모두 한수이고, 1000은 한수가 아니다. 따라서 우리는 세 자릿수가 한수인지 판단하기만 하면 문제가 해결된다. 이는 각 자릿수를 살펴보는 법을 이용하면 된다.(10으로 나눈 나머지를 구하고 10으로 나눈다) 만약 N이 매우 큰 수로 주어진다면 이러한 방법을 이용할 ..
[C++] 백준 7568번 : 덩치 (S5) #문제 https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x,y)로 표시된다. 두 사람 A 와 B의 덩� www.acmicpc.net #풀이 따로 등수를 저장할 배열을 선언해야겠다는 생각을 하는 것이 중요한 문제다. 그리고 각 사람에 대해 그 사람을 제외한 모든 사람과 비교를 해야 하는데, 이는 2중 for문을 이용한다. 본인이 본인과 비교를 하는 경우는 부등호에 등호를 제외시킴으로써 간단하게 제외시킬 수 있다. 그리고 항상 개수를 세는 변수는 for문 앞에서 0으로 초기화해주는 것 잊지 말자. #소스코드 1..
[C++] 백준 2858번 : 기숙사 바닥 (B2) #문제 https://www.acmicpc.net/problem/2858 2858번: 기숙사 바닥 문제 상근이는 기숙사 생활을 한다. 상근이의 방의 크기는 L*W 이다. 수업시간에 타일 채우기 경우의 수를 계산하던 상근이는 자신의 방도 1*1크기 타일로 채우려고 한다. 이때, 가장자리는 빨간�� www.acmicpc.net #풀이 문제를 읽고 문제에서 주어진 조건들을 수식으로 표현해서 적고 살펴보는 것이 중요하다. 그리고 주어진 수식들을 조합하여 얻을 수 있는 식들을 먼저 정리한다. 그리고 코드를 어떻게 구성할지 생각해본다. 이 문제의 경우, 두 가지 수식 WL-(W-2)(L-2)=R, (W-2)(L-2)=B을 통해 WL=B+R, W+L=2+R/2를 얻을 수 있었다. 정답이 유일한 경우만 주어진다고 했으..
[C++] 백준 1436번 : 영화감독 숌 (S5) #문제 https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net #풀이 우선 특별한 풀이법을 생각하기보단 1부터 모든 수를 순서대로 살펴보면 되겠다고 생각하는 것이 중요하다. 그리고 처음 풀이에서 실수했던 것은 6이 3개 이상 존재해야 한다는 점에만 주목해서 연속으로 나타나야 한다는 점을 고려하지 못했다. 그래서 코드를 수정했는데, 이때는 6이 연속으로 3개 존재한다는 것이 확인만 되면 반복문을 탈출하도록 짰다. 연속으로 6이 3개 이상이기만 하면 되..
[C++] 백준 1018번 : 체스판 다시 칠하기 (S5) #문제 https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net #풀이 직사각형에 정사각형을 덧대어 두 사각형의 같은 곳과 다른 곳을 어떻게 check할 것인지에 대해 고민해 봐야 한다. 이 문제는 정사각형이 체스판의 형태로 그 무늬가 규칙적이기 때문에 특별한 방법을 생각해 볼 수 있다. 가로의 인덱스와 세로의 인덱스의 합으로 색을 파악할 수 있다는 점에 주목해보자. 또, 이 문제에서 학습할 중요한 점은 2가지 경우 중 1가지 경우를 구하면, 다..
[C++] 백준 2231번 : 분해합 (B2) #문제 https://www.acmicpc.net/problem/2231 2231번: 분해합 문제 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+ www.acmicpc.net #풀이 특별한 방법을 생각해 내려고 노력하기보다는 1부터 모든 수를 살펴보면 되겠다는 생각을 하는 것이 중요하다. 시간복잡도를 살펴보고 이러한 방법이 가능하다면 지체 없이 이 방법으로 시도해보자. 그리고 여기서 중요한 것은 숫자의 각 자리 수에 접근하는 방법이다. 아래 소스코드 13번째 줄의 for문과 같은 방법의 사용에 익숙해져야 한다.(10으로 나눈 나머지를 구..
[C++] 백준 2798번 : 블랙잭 (B2) #문제 https://www.acmicpc.net/problem/2798 2798번: 블랙잭 문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 �� www.acmicpc.net #풀이 이 문제는 우선 모든 경우를 어떻게 살펴보아야 할 지에 대해 생각해 보아야 한다. N개 중에서 3개를 뽑는 경우를 살펴보아야 하는데, 우리는 순열과 조합을 생각해 볼 수 있다. 여기서는 순서가 중요한 경우가 아니기에 조합(nC3)을 선택하여 탐색한다. 3중for문을 통해 모든 경우를 살피어 M보다 작거나 같고 가장 가까운 수를 찾는다. (만약 100개를 뽑게 된다면 100중 for문을 ..

티스토리툴바