L.O.K

https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net ◎ 문제풀이 단순히 +1 씩 증가시켜 탐색하면 시간초과 나오는 문제이다. 는 x에 M개, y에 N개가 들어갈 수 있으므로 총 M*N개의 경우의 수를 갖는다. M과 N은 최대 40,000이므로 M*N은 1,600,000,000이다. 시간제한 1초는 2억-3억 연산을 수행할 수 있는데 최대연산횟수가 16억이므로 아득히 넘어간다. 위 문제는 수학으로 접근해야 풀린다. M,N이 주어졌을 때, 가 몇 번째에서..

https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net ◎ 문제풀이 채널을 이동하는 경우는 2가지가 있다. 첫번째 경우 : 100번에서 +,-로 이동하는 경우 두번째 경우 : 리모컨 버튼으로 목표채널과 가장 가까운 채널로 이동 후 +,-로 이동하는 경우 두 가지 경우 중 최솟값이 정답이다. 두번째 경우는 브루트포스로 풀어야 한다. 브루트포스는 탐색할 범위를 먼저 정해야 한다. 채널은 0~500,000 까지 있지만 리모컨은 9999.....

https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net ◎ 문제풀이 NXN 크기의 사탕상자를 교환하여 같은 색상이 연속된 사탕개수의 최댓값을 탐색하는 문제이다. 시간제한이 1초인데 N의 최댓값이 50이니 반복문으로 완전탐색해도 시간제한에 걸리지 않는다. 1) 사탕상자에서 연속된 같은 색상 사탕개수의 최댓값을 구하는 함수를 만든다. 2) 인접한 사탕을 교환할 때마다 1)에서 생성한 함수를 호출한다. 브루트포스는 원리는 단순하나 단순한만큼 코드가 길어지므로 구현력을 키워야 한다. ◎ 코드 import sys input = sys.stdin.readline n = int(i..

7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 1. 문제 추상화 A(x, y), B(p, q)에서 x > p 그리고 y > q 이면 A가 B보다 크다고 할 때,입력된 값들의 크기 순위를 매겨라. 순위는 자신보다 큰 수의 개수 + 1이다. 2. 알고리즘 풀이는 쉽지만 문제 뉘앙스가 헷갈릴 여지가 있다. 상식적으로 몸무게가 같고 키가 크면 덩치가 더 크다 말할 수 있다. 그러나 여기서는 아니다. 키와 몸무게가 둘 다 커야 덩치가 큰거다. 문제를 풀 때는 상식이 아닌 조건으로 풀어야 한다. 1. 이차..

2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net 1. 문제 추상화 임의의 값 M이 주어질 때, M의 생성자(N) 중 최소값을 구하라. ( 생성자(N)는 생성자와 생성자 각 자리 수의 합이 M과 같은 수를 의미한다. ) 2. 알고리즘 생성자(N)의 각 자리수의 합을 SUM이라 하겠다. M = N + SUM 이므로 M > N이다. 그러므로 가장 쉬운 방법은 1부터 M까지 모든 경우의 수를 조사하는 방법이다. (브루트 포스) 그러나 M은 1 ≤ M ≤ 1,000,000 이므로 경우의 수..

2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 1. 문제 추상화 주어진 값들 중 세 개를 추출하여 블랙잭 수보다 같거나 작은 최대값을 구하시오. 2. 알고리즘 굉장히 쉬운 문제지만 브루트포스를 몰라 어렵게 풀었다;; 브루트포스(BruteForce)란, Brute( 무식한 )과 Force ( 힘 )의 합성어로 무식한 힘이라는 의미다. 다시 말해서, 무식하게 모든 경우의 수를 탐색하여 조건에 맞는 결과를 내놓는 알고리즘이 효율적일 때가 있다는 말이다. 나는 모든 경우의 수를 조사..