본문 바로가기

완전 탐색 (Brute Force)

 (11)
백준 1748 수 이어 쓰기 1 문제 링크: https://www.acmicpc.net/problem/1748 1748번: 수 이어 쓰기 1 첫째 줄에 N(1≤N≤100,000,000)이 주어진다. www.acmicpc.net 120을 예로 들면, 1부터 120까지 120개의 수가 적어도 한자리씩은 차지한다. 10부터 120까지 120 - 9 = 111개의 수가 적어도 두자리씩은 차지한다. 그리고 100 부터 120까지 120 - 9 - 90 = 21개의 수가 적어도 세자리씩은 차지한다. 따라서 120 + 111 + 21 = 252라는 답을 구할수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include using namespace std; int main() { io..
백준 6064 카잉 달력 문제 링크: https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 문제 최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 로 표현하고, 두 번째 해를 로 표현하였다. 의 다음 해를 표현한 것을 이라고 하자. 만일 www.acmicpc.net i를 y로 시작해서 n씩 증가시키면서 for문을 돌리다가 i를 m으로 나눈 나머지가 x일때의 i값이 답이다. 다시 말해서, 년도의 두번째 숫자..
백준 14500 테트로미노 문제 링크: https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누 www.acmicpc.net 가능한 회전과 대칭을 고려하면 총 19가지 가능한 테트로미노의 모양이 나오고, 전체 종이를 훑으면서 가능한 칸마다 19..
백준 1107 리모컨 문제 링크: https://www.acmicpc.net/problem/1107 불러오는 중입니다... 0번 채널부터 1000000번 채널까지 어느채널에서 가장 적은 수의 버튼을 눌러서 n번 채널로 갈수 있는지 체크하면 된다. 처음에는 isPossible 함수(주어진 채널을 누를때 고장난 버튼이 있는지 확인하는 함수, 주어진 채널이 0일때는 while(num)문이 아예 돌아가지 않기 때문에 예외 처리를 했다.)와 numDigits 함수(주어진 채널로 갈때 눌러야 하는 버튼수를 리턴하는 함수)를 이용해서 아래와 같이 코드를 짰다. 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 3..
백준 1476 날짜 계산 문제 링크: https://www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타내는 수를 E, 태양을 나타내는 수를 S, 달을 나타내는 수를 M이라고 했을 때, 이 세 수는 서로 다른 범위를 가진다. (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19) 우리가 알고있는 1년은 준규가 살고있는 나라에서는 1 1 1로 나타낼 수 있다. 1 www.acmicpc.net 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, ... 에서 1을..
백준 1018 체스판 다시 칠하기 문제 링크: https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 가능한 모든 8 X 8 체스판마다 다시 칠해야 하는 정사각형의 갯수를 세고, 그중 최소값을 구하면 된다. 다시 칠해야 하는 정사각형 갯수의 최소값을 구할때, BWBWB...로 시작하는 보드와 WBWBW...로 시작하는 보드 둘다와 비교해봐야 한다. 아래는 위와 같이 구현하여 처음 AC를 받은 코드이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ..
백준 2503 숫자 야구 문제 링크: https://www.acmicpc.net/problem/2503 2503번: 숫자 야구 첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트라이크 개수를 나타내는 정수와 볼의 개수를 나타내는 정수, 이렇게 총 세 개의 정수가 빈칸을 사이에 두고 주어진다. www.acmicpc.net 각 질문마다 100에서 999중에 가능하지 않은 숫자들을 제거해나가고, 마지막에 남는 숫자들의 갯수를 세면 된다. 100에서 999중에 0이 들어가거나, 숫자가 중복되는경우도 잘 제거해줘야 한다. to_string 함수를 사용해서 숫자를 문자열로 바꿨는데도 불구하고, 0이..
백준 10448 유레카 이론 문제 링크: https://www.acmicpc.net/problem/10448 10448번: 유레카 이론 문제 삼각수 Tn(n ≥ 1)는 [그림]에서와 같이 기하학적으로 일정한 모양의 규칙을 갖는 점들의 모음으로 표현될 수 있다. [그림] 자연수 n에 대해 n ≥ 1의 삼각수Tn는 명백한 공식이 있다. Tn = 1 + 2 + 3 + ... + n = n(n+1)/2 1796년, 가우스는 모든 자연수가 최대 3개의 삼각수의 합으로 표현될 수 있다고 증명하였다. 예를 들어, 4 = T1 + T2 5 = T1 + T1 + T2 6 = T2 + T2 or 6 = T www.acmicpc.net 삼각수 = 1, 3, 6, 10, 15, .... n번째 삼각수 = n * (n + 1) / 2 45번째 삼각수 = ..

티스토리툴바