브루트포스 알고리즘22 [백준 03507] Automated Telephone Exchange [Java] 문제 In St Petersburg phone numbers are formatted as “XXX–XX–XX”, where the first three digits represent index of the Automated Telephone Exchange (ATE). Each ATE has exactly 10 000 unique phone numbers. Peter has just bought a new flat and now he wants to install a telephone line. He thinks that a phone number is lucky if the arithmetic expression represented by that phone number is equal to zero.. 2023. 11. 27. [백준 14888] 연산자 끼워넣기 [Python] 풀이 N개의 수에 대해 N - 1개의 수식을 적용해 모든 경우를 생각해도 크기가 작아 충분하다. 하지만, 연산자 우선순위에 관계없이 왼쪽부터 오른쪽으로 연산을 하면 되기 때문에 중복해 계산하는 부분이 있다. 이 부분에 대한 값을 stack에 저장해 재사용 하는 방법으로 풀이했다. 0 ~ N-1 번의 index에 대한 탐색이 끝났다면, 최댓값과 최솟값을 갱신해주고, 그렇지 않은 경우에는 아직 사용할 수 있는 연산자에 대해 계산을 해주자. 소스코드 소스코드 보기 출처 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의.. 2023. 7. 22. [백준 27172] 수 나누기 게임 [Java] 풀이 N명의 플레이어가 가진 카드에 대해서 서로 다른 플레이어의 카드 간 배수가 존재하는지 판별하는 문제다. 문제에서 두 번 이상 등장하는 카드는 없다고 하니 해당 번호의 카드의 존재여부를 기록해두면 쉽게 풀이할 수 있다. N명의 player에 대해 카드 번호를 입력받고 i번째 플레이어가 가진 카드가 있다고 표시해주자. 그 다음에는 N명의 player가 가진 카드의 배수에 해당하는 카드가 있는지 확인해주면 된다. 만약 카드 숫자가 i 일 때 카드 숫자가 j 인 카드가 있다면, j % i == 0 즉 j는 i의 배수다. 만약 최대 숫자 1,000,000 (SIZE - 1) 에 대해 i 배수를 탐색했는데 만족하는 카드가 없다면, i 카드를 가진 player는 점수를 얻을 수 없다. 점수를 score 배열에 .. 2023. 7. 13. [백준 4375] 1 [Java] 풀이 입력받은 정수 n의 배수 중 1로만 이루어진 배수를 찾아 자릿수를 출력하면 되는 문제다. 간단하게 1부터 시작해서 n으로 나누어 떨어질때까지 숫자 뒤에 1씩 붙여주면 된다. 뒤에 숫자 1을 붙일 때 마다 자릿수를 한 개씩 증가시켜 주자. 소스코드 소스코드 보기 출처 4375번: 1 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 각 자릿수가 모두 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오. www.acmicpc.net 2023. 6. 29. [백준 17106] 빙고 [Text] 풀이 빙고를 풀면 된다. 뭔... 구분을 위해 아래와 같이 표를 만들었다. 우선 조건없이 색칠 가능한 칸을 찾아보자. 이제부턴 추리를 해야한다. C1이 참이라 가정을 해보자. A1, B2, C3, D4, E5가 참이여야 한다. B2에 의해 최소 한개의 세로 빙고줄이 있어야 하지만, B1에 의해 E1은 색칠될 수 없고, D3의 조건에 부합하지 못해 결국 아무런 세로 빙고줄이 만들어지지 않는다. C1이 아니므로 불가능 표시(검정색)를 해주었고, 다음으로 A1이 성립하지 않는경우로 추리해보겠다. E2는 진행에 따라 다르니 일단 C4가 참이라고 가정하고 계속 진행해보겠다. E2와 E3만 성립한다면, B2는 참이다. 일단은 아직까지는 전부 성립한다. 남은 칸들에 대해 진행을 해보자. D3이 성립하는지 살펴보자. .. 2023. 6. 10. [백준 20529] 가장 가까운 세 사람의 심리적 거리 [Java] 풀이 N개의 중 3개의 MBTI에 대해서 가장 작은 심리적 거리를 구해야 한다. 모든 경우의 수를 전부 탐색하면 N^3 이기에 당연히 시간초과가 발생할 것이다. 때문에 구한 거리가 0인지 확인을 하고, 중간에 loop를 빠져나와야 한다. 비둘기집 원리를 통해 더 줄여보자. MBTI에 대한 심리적 거리의 최선의 경우는 뭘까? bruteforce이지만, 심리적 거리가 0인 경우 더 이상의 탐색이 무의미하기에 중단 해주어 시간초과가 발생하지 않는다. 심리적 거리가 0이라는 조건 이후의 탐색이 무의미하다면, 심리적 거리가 0이 되는 최악의 경우는 무엇일까? 바로 비둘기집 원리에 따른 33명이다. 서로 다른 MBTI를 가진 16명이 2명씩 총 32명 있을 경우 심리적 거리는 0이 될 수 없다. 33명부터 동일한 .. 2023. 6. 7. 이전 1 2 3 4 다음
