>알고리즘 문제
1. 타겟넘버
1)문제
n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.
제한사항- 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
- 각 숫자는 1 이상 50 이하인 자연수입니다.
- 타겟 넘버는 1 이상 1000 이하인 자연수입니다.
2)솔루션
class Solution {
fun solution(numbers: IntArray, target: Int): Int {
var answer = 0
val arr=numbers.mapTo(ArrayList<Int>()){it}
return find(arr,target)
}
fun find(nums:ArrayList<Int>, target:Int):Int{
var result=0
if(nums.isEmpty()){
if(target==0) return 1
else return 0
}
val tmps=nums.clone() as ArrayList<Int>
val tmp=tmps[0]
tmps.removeAt(0)
result+=find(tmps,target+tmp)+find(tmps,target-tmp)
return result
}
}-ArrayList에 숫자들을 넣고 앞에서부터 해당 숫자를 더하는 경우와 빼는 경우를 각각나누어 체크해서 결과들중 타겟과 같은 값이 나오는 경우의 수를 합친다.
2. 짝수 행 세기
1)문제
모든 수가 0 또는 1로 이루어진 2차원 배열 a가 주어집니다. 다음 조건을 모두 만족하는 2차원 배열 b의 경우의 수를 (107 + 19)로 나눈 나머지를 return 하도록 solution 함수를 완성해주세요.
- b의 모든 원소는 0 아니면 1입니다.
- a의 행/열의 개수와 b의 행/열의 개수가 같습니다. (= a와 b의 크기가 같습니다.)
- i = 1, 2, ..., (a의 열의 개수)에 대해서 a의 i번째 열과 b의 i번째 열에 들어 있는 1의 개수가 같습니다.
- b의 각 행에 들어 있는 1의 개수가 짝수입니다. (0도 짝수입니다.)
제한 사항
- a의 행의 개수는 1 이상 300 이하입니다.
- a의 각 행의 길이는 1 이상 300 이하로 모두 동일합니다.
입출력 예
a result
| [[0,1,0],[1,1,1],[1,1,0],[0,1,1]] | 6 |
| [[1,0,0],[1,0,0]] | 0 |
| [[1,0,0,1,1],[0,0,0,0,0],[1,1,0,0,0],[0,0,0,0,1]] | 72 |
2)솔루션
class Solution {
fun solution(a: Array<IntArray>): Int {
var answer: Int = -1
var coln=IntArray(a[0].size){0}
val row=a.size //행 개수, 세로길이
val col=a[0].size //열 개수, 가로길이
for(i in a[0].indices){
var sum=0
for(j in a.indices){
sum+=a[j][i]
}
coln[i]=sum
}
val mod=10000019
val c=Array(row+1){IntArray(row+1)} //파스칼 항등식을 이용해 rowCrow까지 연산해서 저장해둠, c[n][r]=nCr
c[0][0]=1
for(i in 1..row){
for(j in 0..i){
if(i==j||j==0) c[i][j]=1
else c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod
}
}
val dp=Array(col){IntArray(row+1){0}} //dp[선택된 열][까지의 짝수행 개수]
dp[0][row-coln[0]]=c[row][row-coln[0]] //열의 원소는 row개. 그중 짝수행인 0의 자리를 고르는 경우의수
for(i in 0..col-2){
for(j in 0..row){
if(dp[i][j]==0) continue
val oddr=row-j
val min=maxOf(0,coln[i+1]-oddr)
val max=minOf(j,coln[i+1])
for(k in min..max){
val next=coln[i+1]-k +(j-k)
val case=(c[j][k].toLong()*c[row-j][coln[i+1]-k].toLong())%mod.toLong()
dp[i+1][next]+=((dp[i][j].toLong()*case)%mod.toLong()).toInt()
}
}
}
return dp[col-1][row]
}
}<1>우선 각 열마다 1의 수를 구해서 저장: coln[]
<2>나올 수 있는 조합을 미리 구해서 배열에 저장: 이때 일일히 구하는게 아닌 파스칼 항등식을 이용해서 구한다. :c[][]
=>조합의 경우 구하는데 시간이 걸리고 그 수가 매우 커지기 때문에 미리 합동식 성질을 이용해서 mod값으로 나눈 값들을 저장한다.
<3>이제 dp초기 세팅
-dp[i][j]: 0부터 i번째 열까지만 고려했을때 원소의 합이 짝수인 행 개수가 j개인 경우의 수.
-시작은 0번째 열부터: 0번째 열까지만 고려하므로 각 행별 원소는 하나뿐. 즉, 원소가 0이면 짝수행, 1이면 홀수행이다.
-그러므로 짝수행의 개수는 전체 행의 개수에 0번째 열의 1의 개수를 뺀값
-경우의 수는 전체 행에서 짝수행의 자리를 고르는 수: rowC(row-coln[0])
=>dp[0][row-coln[0]]=c[row][row-coln[0]]
<4>dp시작
-방식은 짝수행에 1을 몇개 분배할지 골라서 그 결과 짝수행이 몇개가 나오는지 확인후 dp[i+1][]을 채우는것
-i열까지 체크해서 i+1을 구성시켜주는 방식으로 진행 되므로 열에 해당하는 i는 1부터 col-2까지
-j는 i열까지 짝수행의 수니까 0부터 row까지
-dp[i][j]에 대해 그 값이 0이면 continue: 경우의 수가 없다는 뜻이므로 dp[i][j]로 부터 dp[i+1][]의 경우의 수를 구할 수 없음
-k는 1을 분배하기 위해 고른 짝수행의 수:
=>k의 최소: 만약 홀수행에 1을 다 분배하고도 남으면 짝수행에도 분배되어야 하므로 maxOf(0,coln[i+1]-(row-j))
=>k의 최대: 짝수행이 j개니깐 j개까지 가능하나 1의 개수가 모자를수도 있으므로 minOf(j,coln[i+1])
-k를 해당범위에서 for문을 돌리며 경우의 수와 짝수행 수를 구함
-다음 열(i+1)까지 고려했을시 짝수행의 수:(홀수행에 1이 분배된 수)+(짝수행에 1이 분배되지 않은 수)=(coln[i+1]-k)+(j-k)
=>이 값을 next로 두자
-경우의수
=>홀수행에서 1분배하고 짝수행에서 1분배하는 경우의 수: case=(row-j)C(coln[i+1]-k) + jCk
=>최종 경우의수는 dp[i][j]까지의 경우의 수와 곱연산: dp[i][j]*case
-경우의 수를 dp에 더해줌: dp[i+1][next]= dp[i][j]*case
@주의할점: 모든 곱연산에 toLong으로 Long으로 형변환하기=>int값 범위에 벗어나는 경우가 있기때문
-최종적으로 문제 조건은 모든 행이 짝수행이어야 한다고 했으니 답은 dp[col-1][row]
>개인프로젝트 디자인 구상
'코틀린-안드로이드' 카테고리의 다른 글
| 35일차)알고리즘 문제(주차요금 계산) (0) | 2024.06.28 |
|---|---|
| 34일차)알고리즘 문제(k진수에서 소수 개수 구하기, 짝수행 세기, 쌍둥이 빌딩 숲, 지형 이동), 코드카타 리뷰(숫자 k진수 변환, 정규표현식) (0) | 2024.06.27 |
| 32일차)알고리즘 문제(피로도), 챌린지반 강의 1회차, 추가 과제 (0) | 2024.06.25 |
| 31일차)알고리즘 문제(프로세스, 등산코스 정하기, 징검다리), 개인프로젝트 구상 (0) | 2024.06.24 |
| 30일차)알고리즘 문제(기능개발, 카운트 다운) (0) | 2024.06.23 |