목록SWEA (25)
시간이 NullNull
문자열 P는 스스로를 계속 복제해서 매우 긴 문자열이 되었다. 복제하는 방법은 다음과 같다. P0 = “0” Pi+1 = Pi + “0” + f(g(Pi)) 여기서, f(A) 함수는 문자열 A의 모든 문자를 반전시킨다. 예를 들어서, f(“10110”) = “01001”이다. g(A)함수는 문자열 A를 좌우 반전 시킨다. 예를 들어서, g(“10110”) = “01101” 이다. 위와 같은 복제 방법을 무한히 반복한 문자열 P의 K번째 문자가 무엇인지 구하여라. P1 = “001” P2 = “0010011” P3 = “001001100011011” 위와 같이 복제가 이루어질 것이다. 따라서 3번째 문자는 1, 7번째 문자는 1, 10번째 문자는 0이다. 이 문제는 문자들의 규칙을 보고 점화식만 세워서 ..
숫자는 다양성을 가지고 있다. 다양성이란, 숫자를 구성하는 수의 종류를 의미한다. 예를 들어서 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..
준환이는 N개의 서로 다른 무게를 가진 무게 추와 양팔저울을 가지고 있다. 모든 무게 추를 양팔저울 위에 올리는 순서는 총 N!가지가 있고, 여기에 더해서 각 추를 양팔저울의 왼쪽에 올릴 것인지 오른쪽에 올릴 것인지를 정해야 해서 총 2N * N!가지의 경우가 있다. 하지만 양팔 저울에 갑자기 문제가 생겨서 무게 추를 올릴 때 오른쪽 위에 올라가 있는 무게의 총합이 왼쪽에 올라가 있는 무게의 총합보다 더 커져서는 안 된다. 예를 들어 무게추가 총 3개, 무게가 각각 1, 2, 4 라고 하면 아래 그림처럼 총 15가지 경우가 나올 수 있다. 이런 방법으로 준환이가 양팔 저울에 모든 무게추를 올리는 방법은 총 몇 가지가 있을까? 이 문제의 경우 앞 문제에서 언급한 DFS에서 static field를 많이 언..