코딩하는 두꺼비

www.acmicpc.net/problem/1520

처음엔 그냥 DFS로 풀려고 했지만 계속 시간 초과가 나와서 고민을 많이 했다. 그냥 DFS를 사용하면 4^(500*500)번의 연산 횟수가 나온다는 것을 잘 몰랐다..

결국 풀다가 도저히 안되서 답을 보고 풀 수 있었는데 DP를 bottom up형식으로 써야하는 것이 어려웠던 문제이다.

문제 해설 중에는 이 블로그가 이해를 하는데 많이 도움을 준 것 같다.

wootool.tistory.com/83

결국 내가 푼 코드는

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
using namespace std;

int map[501][501];
int dp[501][501];
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
int m, n;

int dfs(int x, int y) {
	if (!x && !y) {
		return 1;
	}
	if (dp[x][y] == -1) {
		dp[x][y] = 0;
		for (int i = 0; i < 4; i++) {
			int a = x + dx[i];
			int b = y + dy[i];
			if (a >= 0 && b >= 0 && a < m && b < n &&
				map[a][b] > map[x][y]) {
				dp[x][y] += dfs(a, b);
			}
		}
	}
	return dp[x][y];
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> m >> n;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			dp[i][j] = -1;
		}
	}
	cout << dfs(m-1, n-1);
	return 0;
}

DP를 이런식으로 사용할 수 도 있다는 것을 알 수 있었고 아직 부족함을 많이 느끼게 해준 문제였다.. ㅠㅠ

예전에 자바로 구현해보았던 부분이지만 다시 만들어보니 생각보다 시간이 좀 걸렸다..

1. build.gradle의 dependencies에 코드를 추가한다.

dependencies {

    implementation 'com.google.android.material:material:1.2.1'

}

2. Floating Action Button을 추가하고자 하는 xml의 버튼 디자인 중 해당 버튼을 찾아 추가해준다.

<com.google.android.material.floatingactionbutton.FloatingActionButton
        android:id="@+id/fab"
        android:layout_width="60dp"
        android:layout_height="60dp"
        app:fabCustomSize="60dp"
        android:clickable="true"
        android:focusable="true"
        app:layout_constraintBottom_toBottomOf="parent"
        app:layout_constraintEnd_toEndOf="parent"
        app:layout_constraintHorizontal_bias="0.919"
        app:layout_constraintStart_toStartOf="parent"
        app:layout_constraintTop_toTopOf="parent"
        app:layout_constraintVertical_bias="0.937"
        app:srcCompat="@drawable/add" />

여기서 보통은 백그라운드 이미지가 제대로 중앙에 오지 않을 것이다. 이때!

app:fabCustomSize="60dp"

width와 height 크기에 맞추어 위의 dp를 조절해 코드를 추가해주면 해결이 된다ㅎㅎ

3. 버튼을 추가한 xml을 사용하는 액티비티로 가서 새로운 액티비티를 열어주는 버튼 클릭 리스너 코드를 추가한다.

package com.example.desktop.mymo

import android.content.Intent
import androidx.appcompat.app.AppCompatActivity
import android.os.Bundle
import android.view.View
import com.google.android.material.snackbar.Snackbar

class MainActivity : AppCompatActivity() {
    override fun onCreate(savedInstanceState: Bundle?) {
        super.onCreate(savedInstanceState)
        setContentView(R.layout.activity_main)

        val fab: View = findViewById(R.id.fab)		// 버튼 객체 생성
        fab.setOnClickListener {					// 클릭 리스너 생성
            val intent = Intent(this, EditActivity::class.java)	//인텐트 생성
            startActivity(intent)				//새로운 액티비티 시작
        }
    }
}

위의 과정을 거치면

위와 같은 FAB를 만들 수 있다.

다음 번엔 버튼 색깔 및 버튼 눌렀을 때 여러개의 버튼이 나오는 방법에 대해 공부를 해봐야겠다..

예전에 안드로이드 스튜디오를 처음 사용할때도 찾아봤던 내용이다. 맨날 헷갈려서 이번에는 기록해보려고 한다.

처음 시작할 경우 앱의 액션바가 보이지 않는 경우가 있다.

그때는 xml에 들어가 눈모양에서 "Show System UI"를 클릭해주면 나온다ㅎㅎ