python 하면서 신경 쓰지 않던 형변환을 신경쓰려니 머리가 너무 아팠다…
1629번 A를 B번 곱한 뒤 C 모듈러 연산하기
이건 kotlin 문제는 아니고… 그냥 못 풀었다.ㅠㅠ 지수법칙으로 문제를 풀어야한다는 생각 자체를 못했다 O(N) - > O(logN) 으로 줄일 수 있는 문제…. kotlin도 이런식으로 언패킹이 된다! 왜지?ㄷㄷ pair와 triple 때문은 아닌것같은데… 아니 맞나? 연산할때 형을 꼭 맞춰줘야하는 것은 파이썬에 익숙해진 나는 적응이 안된다ㄷㄷ…. 숫자 뒤에 L을 쓰면 Long 이라는 의미. toLong() 을 안하고 이렇게 표현가능하구나~
fun main() = with(System.`in`.bufferedReader()) {
var (a, b, c) = readLine().split(' ').map { it.toLong()}
var result = 1L
if(b == 1L) {
print(a % c)
}
else {
while (b != 1L) {
if (b % 2 == 0L) {
a = (a * a) % c
b /= 2
} else {
// 4^ 15 = 4 * 4^14 = 4 * 16^7 = 4 * 16 * (16^2)3
result = (result * a) % c
a = (a * a) % c
b /= 2
}
}
print((result * a) % c)
}
}
더 멋진 풀이…
while (exp > 0) {
if (exp % 2 == 1L) {
result = (result * base) % z
}
base = (base * base) % z
exp /= 2
}
println(result)
반복문이 아닌 재귀로 푸는게 더 멋져보인다.
fun main() {
val br = System.`in`.bufferedReader()
val (A, B, C) = br.readLine().split(" ").map { it.toInt() }
println(pow(A, B, C))
}
fun pow(a: Int, b: Int, mod: Int): Long {
if (b == 0) return 1
val n = pow(a, b /2, mod)
if (b % 2 == 0)
return n * n % mod
else
return (n * n % mod) * a % mod
}
1992번 쿼드 트리(흑백 영상 압축법)
종이 자르기 문제랑 똑같아서 금방 풀 줄 알았는데 2시간이나 걸렸다. kotlin 진짜… char를 Int로 바꾸려면 char.toInt() 바로하면 아스키코드가 나와서 char.toString().toInt()로 바꿔야함!! 이것땜에 시간 엄청 썼다ㅠ.ㅠ 그리고 신기한게 readLine()으로 입력받으면 Array가 아니라 List 로 받아오나보다. List는 불가변… 뭐 건드릴 일이 없으니까 괜찮겠지?
fun main() = with(System.`in`.bufferedReader()) {
val n = readLine().toInt()
val video = Array(n) { readLine().map { it.toString().toInt() } }
var result = compress(0, 0, n, video)
print(result)
}
fun compress(row : Int, col : Int, size : Int, video : Array<List<Int>>) : String {
var ans = ""
var s = 0
for (i in row until row + size) {
for (j in col until col + size) {
s += video[i][j]
}
}
if (s == 0) {
return "0"
} else if (s == size * size) {
return "1"
}
ans += compress(row, col, size/2, video)
ans += compress(row, col+size/2, size/2, video)
ans += compress(row+size/2, col, size/2, video)
ans += compress(row+size/2, col+size/2, size/2, video)
return "("+ans+")"
}
1074번 2차원 배열 Z 모양으로 방문하기
2시간 걸림. 왼쪽 아래 부분에 col < col + 2~ 인데 col < 2~ 로 해서 처음에 틀려서 이거 찾아내는데 1시간 걸림;; 보자마자 4등분 재귀라고 생각해서 품… O(log(4)N) 임.
import kotlin.math.*
fun main() = with(System.`in`.bufferedReader()) {
val (n, r, c) = readLine().split(' ').map { it.toInt() }
var cnt = 0
// 4등분 중 어디있는지 알아야함.
// n = 3이면, 2^2 * 2^2 로 4등분 됨
// 2^(pow-1) * 2^(pow-1) = 2^(2pow-2)
fun zig(pow : Int, row : Int, col : Int) {
if(pow == 0){
return
}
if(r >= row && r < row + 2.toDouble().pow(pow-1)) {
// 왼쪽 위
if(c >= col && c < col + 2.toDouble().pow(pow-1)) {
zig(pow - 1, row, col)
}//오른쪽 위
else {
cnt += 2.toDouble().pow(pow-1).pow(2).toInt()
zig(pow - 1, row, col + 2.toDouble().pow(pow-1).toInt())
}
}
else {
//왼쪽 아래
if(c >= col && c < col + 2.toDouble().pow(pow-1)){
cnt += (2.toDouble().pow(pow-1).pow(2).toInt() * 2)
zig(pow - 1, row + 2.toDouble().pow(pow-1).toInt(), col)
}
//오른쪽 아래
else{
cnt += (2.toDouble().pow(pow-1).pow(2).toInt() * 3)
zig(pow - 1, row + 2.toDouble().pow(pow-1).toInt(), col + 2.toDouble().pow(pow-1).toInt())
}
}
}
zig(n, 0, 0)
print(cnt)
}
근데 이걸 200바이트로 푼 사람은 뭐지? 내가 이상한게 푼건가ㅠ_ㅠ 이거 밖에 없어보이는데…
fun main() {
val (n, r, c) = readLine()!!.split(" ").map { it.toInt() }
println(solve(n, r, c))
}
private fun solve(n: Int, r: Int, c: Int): Int {
if(n == 0) return 0
return 2 * (r % 2) + (c % 2) + 4 * solve(n - 1, r / 2, c / 2)
}
와 이건 어떻게 해석을 해야…. 와 천재적이다 진짜;; 이건 이해도 잘 안된다. 보내주자 ㅠ_ㅠ
private fun z(n: Int, r: Int, c: Int): Int {
if (n == 0) return 0
val half = 1 shl (n - 1)
return if (r < half && c < half) z(n - 1, r, c)
else if (r < half && c >= half) half * half + z(n - 1, r, c - half)
else if (r >= half && c < half) 2 * half * half + z(n - 1, r - half, c)
else 3 * half * half + z(n - 1, r - half, c - half)
}
이게 더 깔끔하다. 1 shl (n-1) 의 의미 : 1 x 2^(n-1) = 변의 길이 나는 이걸 2.toDouble().pow(pow-1) 로 표현해서 엄청 지저분했군 ㅠ_ㅠ 그리고 나는 z(n,0,0) 을 초기 값으로 줬는데 z(n,r,c) 로 초기 호출하고 재귀할때 half를 빼주는게 더 맞아보인다…