문제 설명

A 의 수열이 있을 때, |Ai - Ai+1| ~ |An-2 - An-1| 의 합 중 최대값을 구하면 된다.

풀이

완전 탐색으로 다 확인했다.
1. O(N!) 이여서 그렇게 오래 걸리지도 않는다.
사용한지 안한지는 비트마스크를 이용해서 했다.

코드

시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초256 MB47832862226761.303%

문제

N개의 정수로 이루어진 배열 A가 주어진다. 이 때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최대값을 구하는 프로그램을 작성하시오.

|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|

입력

첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.

출력

첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 출력한다.

예제 입력 1 

6
20 1 15 8 4 10

예제 출력 1 

62

출처


문제 설명

1. Mi 의 숫자가 N 에 존재하는지 출력하는 문제

풀이

1. 이분탐색을 사용하라고 문제 분류가 돼있지만, 더 빠른 풀이를 위해 BitSet 을 사용했다.
2. 이분탐색을 사용하면 O(MlgN + NlgN) 정렬하고 찾는 시간이고, BitSet 을 사용하면(N+M) 이다.
3. 메모리 제한도 높고, Mi 의 제한도 높지 않아서 쉽게 풀 수 있었다.
4. JAVA 로 약 680MS 로 정답이니 거의 엄청 빠른 퍼포먼스를 낼 수 있었다. (첫 제출은 790MS 정도였다. 이유는 숫자 + 문자열을 write 해줬기 때문이다. 변경된 것은 문자열로만 되게)

코드

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 숫자 M개가 주어졌을 때, 이 숫자가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N (1 ≤ N ≤ 500,000)이가 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 숫자가 주어진다. 숫자 카드에 적혀있는 숫자는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 숫자가 적혀있는 경우는 없다.

셋째 줄에는 M (1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 숫자가 주어지며, 이 숫자는 공백으로 구분되어져 있다. 이숫자도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다

출력

첫째 줄에 입력으로 주어진 M개의 숫자에 대해서, 각 숫자가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

예제 입력 1 

5
6 3 2 10 -10
8
10 9 -5 2 3 4 5 -10

예제 출력 1 

1 0 0 1 1 0 0 1

출처


1. 메모리 제한이 8MB 인 문제

2. 자바는 boolean 배열을 사용해도 되지만, 다른 언어는 되지 않는다.

3. 자바에서 제공하는 BitSet 이라는것을 사용하지 않을 시, int 배열을 만들어서 쪼개고 쪼개고 넣으면 될 것 같다.

문제

문제: N개의 정수 A1, A2, ..., AN 을 읽고, 이들 중에서 반복되는 수를 제외하고 남은 N'개의 수 B1, B2, ..., BN’ 을 입력된 순서대로 출력하시오. 이때,

  1.  Ai < 225 = 33554432, i=1,2,…,N.
  2. 입력의 갯수 N은 1 이상 500만 이하이다.

입력

첫째 줄에 A1, A2, ..., AN이 주어진다.

출력

B1, B2, ..., BN’을 출력한다.

예제 입력 1 

12 1 449 12 555 1201 912 555 19372

예제 출력 1 

12 1 449 555 1201 912 19372

예제 입력 2 

21003957 20891590 11382885 18340118 11354168 5461061 12693617 2552341 14639514 25224366 19239852 136782 17206566 18675414 9536557 24961835 2507460 32083310 4485200 19506627 21087117 9270314 12953612 10216350 8170712 20436397 11382885 29305594 27169105

예제 출력 2 

21003957 20891590 11382885 18340118 11354168 5461061 12693617 2552341 14639514 25224366 19239852 136782 17206566 18675414 9536557 24961835 2507460 32083310 4485200 19506627 21087117 9270314 12953612 10216350 8170712 20436397 29305594 27169105

힌트

메모리 제한에 유의하시오.


1. 비트마스크 문제

2. 1 << 6 를 하면 6자리 비트가 생긴다.

3. 그 비트로 a~f 의 열쇠가 있는지 검사하고, 찾으면 넣는다.

4. visited 에는 위치, 보유한 열쇠의 이동거리값이 들어있다.

문제

지금 민식이가 계획한 여행은 달이 맨 처음 뜨기 시작할 때 부터, 준비했던 여행길이다. 하지만, 매번 달이 차오를 때마다 민식이는 어쩔 수 없는 현실의 벽 앞에서 다짐을 포기하고 말았다.

민식이는 매번 자신의 다짐을 말하려고 노력했지만, 말을 하면 아무도 못 알아들을 것만 같아서, 지레 겁먹고 벙어리가 되 버렸다. 결국 민식이는 모두 잠든 새벽 네시 반 홀로 일어나, 창 밖에 떠있는 달을 보았다.

하루밖에 남지 않았다. 달은 내일이면 다 차오른다. 이번이 마지막기회다. 이걸 놓치면 영영 못간다.

영식이는 민식이가 오늘도 여태것처럼 그냥 잠 들어버려서 못 갈지도 모른다고 생각했다. 하지만 그러기엔 민식이의 눈에는 저기 뜬 달이 너무나 떨렸다.

민식이는 지금 미로 속에 있다. 미로는 직사각형 모양이고, 여행길을 떠나기 위해 미로를 탈출하려고 한다. 미로는 다음과 같이 구성되있다.

  • 빈 곳 : 언제나 이동할 수 있다. ('.‘로 표시됨)
  • 벽 : 절대 이동할 수 없다. (‘#’)
  • 열쇠 : 언제나 이동할 수 있다. 이 곳에 처음 들어가게 되면 열쇠를 집는다. (소문자 a - f)
  • 문 : 대응하는 열쇠가 있을 때만 이동할 수 있다. (대문자 a - f)
  • 민식이의 현재 위치 : 빈 곳이고, 민식이가 현재 서 있는 곳이다. (숫자 0)
  • 출구 : 달이 차오르기 때문에, 민식이가 가야하는 곳이다. 이 곳에 오면 미로를 탈출한다. (숫자 1)

달이 차오르는 기회를 놓치지 않기 위해서, 되도록 미로를 탈출하려고 한다. 한 번의 움직임은 현재 위치에서 수평이나 수직으로 한 칸 이동하는 것이다.

민식이가 미로를 탈출하는데 걸리는 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (N,M <= 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, 영식이가 열쇠를 숨겨놓는 다면 문에 대응하는 열쇠가 없을 수도 있다. 0은 한 개, 1은 적어도 한 개 있다. 그리고, 열쇠는 여러 번 사용할 수 있다.

출력

첫째 줄에 민식이가 미로를 탈출하는데 드는 이동 횟수의 최솟값을 출력한다. 만약 민식이가 미로를 탈출 할 수 없으면, -1을 출력한다.


1. 백트래킹을 하는 문제

2. 열, 그룹, 행에 그 숫자가 들어가는걸 확인하는건 비트마스크로 처리

문제

스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 몇 몇 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.

나머지 빈 칸을 채우는 방식은 다음과 같다.

  1. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
  2. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.

또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈 칸에는 3이 들어가야 한다.

이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.

게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.

입력

아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.

출력

모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.

스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.


+ Recent posts