목록sw expert (11)
시간이 NullNull
숫자는 다양성을 가지고 있다. 다양성이란, 숫자를 구성하는 수의 종류를 의미한다. 예를 들어서 1512 라는 숫자는 ‘1’, ‘5’, ‘2’로 구성되어 있기 때문에 다양성이 3이다. 숫자가 주어졌을 때 그 숫자의 다양성을 구하는 프로그램을 작성하라. 이 문제의 경우 단순하게 다양성이 최소 1 ~ 10이란 것을 알 수 있다. 이를 이용하여 boolean[] 배열 10개를 만들어서 아직 숫자가 나오지 않았을 경우( boolean 배열의 값이 false 인 경우 ) cnt를 증가시키면 된다. 이를 코드로 나타내면 간단하게 다음과 같이 나온다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader..
콩을 사랑하는 민석이의 취미는 n*m 크기의 사각형 밭에 콩을 늘어놓는 것이다. 한 칸에 콩 하나씩을 놓을 수 있는데, 2가 싫은 민석이는 콩들 사이의 길이가 2가 되지 않도록 하면서 최대한 많은 콩을 놓으려고 한다. 예를 들어 다음과 같이 콩을 배치할 수 없다. 콩1(x1, y1)과 콩2(x2, y2) 사이의 길이는 이다. 민석이를 도와서 사각형 밭에 최대로 콩을 늘어놓자. 이 문제의 경우 처음에는 콩을 배치하고 규칙을 위반하였는지 확인하여하지 않았다면 모든 경우 중에서 규칙을 위반하지 않고 콩이 최대로 많은 경우가 생길 때 콩의 개수를 세는 것이라 생각하였다. 하지만 밑에 가로와 세로의 길이가 주어지게 되는데 최대가 각각 1000이며 이경우 1000 * 1000 이 되어 결국 모든 경우를 다 보기엔 ..
삼성 1:1 프로그래밍 리그의 시즌이 끝났다. 앨리스는 B전 A승, 밥은 D전 C승이다. 누구의 승률이 더 높은가? 이 문제의 경우 이게 왜 D3일까 고민할 정도로 너무 간단한 문제였다. 하지만 아무 생각없이 제출을 하지 시간초과가 떴었고 이후 내 쓰는 라이브러리가 바뀌게 되는 결과가 나왔다. 중요 포인트는 자바의 경우 10만 개의 케이스를 실행시키는데 2초. 이것을 모른 채로 풀었었는데 한참뒤에 깨닫고 시간을 줄이는 방법을 생각해보았으나 로직에는 아무 문제가 없고 결국 입력과 출력의 방식에 차이가 있다는 것을 깨달았다. 맨 처음 내가 시도했던 코드이다. import java.util.Scanner; public class Solution { public static void main(String[] a..
048이라는 추억의 게임을 아는가? 2048은 한 때 유명했던 1인용 게임으로, 격자 위에서 숫자가 적힌 타일들을 밀어서 합치고 최종적으로 2048을 만들어 내는 것이 목표인 게임이다. 한번 타일을 밀 때는 상하좌우를 정해서 밀어야 한다. 방향을 정하면 격자 위에 있는 모든 타일이 그 방향으로 밀린다. 만약 어떤 타일이 밀리는 방향에 다른 타일이 있고, 두 타일에 적힌 숫자가 같다면 두 타일은 합쳐져 새로운 하나의 타일이 되고 이 타일에 적힌 숫자는 합쳐진 숫자들의 합이 된다. 이렇게 합쳐져서 만들어진 새로운 타일은 숫자가 같은 다른 타일이 밀려와도 합쳐져서는 안 된다. 만약 같은 숫자가 적힌 타일이 세 개 이상 있을 때는 헷갈리는 경우를 없애기 위해 빨리 벽에 닿게 될 타일을 먼저 민다고 생각한다. 예..
성수는 이제 프로그래밍을 시작하기로 마음 먹은 초보다. 그렇기에 프로그래밍 강좌를 통해 자신의 프로그래밍 실력을 끌어 올리려고 한다. 성수의 실력이 A라고 할 때, 수준이 M인 강좌를 시청하고 나면 성수의 실력은 (A+M)/2가 된다. 즉, 성수는 자신이 보는 강좌가 좋은 지 아닌지 판단하지 않고 그대로 강좌를 받아들이기 때문에, 실력보다 낮은 수준의 강좌를 보면 실력이 낮아질 수 있다. 현재 성수는 아직 아무런 실력이 없다. 즉 실력이 0이다. 성수는 볼 수 있는 강좌 총 N개 찾았고 시간 문제상 이 중에서 K개를 적절한 순서로 선택해 한 번씩 시청하려고 한다. 성수가 같은 강좌를 두 번 이상 보는 일은 없다고 할 때, 성수가 가질 수 있는 실력의 수치는 최대 몇인지 구하는 프로그램을 작성하라. 이 문..